책장 만들기 1초 128MB
문제
수 십년에 걸친 노력 끝에 N권의 책을 모은 정올도서관의 도서관장은 이 책들을 보관할 책장을 만들고자 한다.
각 i번째 책에 대하여 Wi의 너비와 Hi의 높이를 가진 N권의 책들이 1부터 i번째까지 있을 때, 이 책들은 반드시 연속된 순서대로 선반에 놓여야 한다.
예를 들어, 첫 선반에 1...k 책이 있다면, 두 번째 선반은 k+1 책부터 시작하는 형식이다.
각 선반의 총 너비는 최대 L이며, 선반의 높이는 해당 선반에서 가장 높은 책의 높이와 동일하고, 전체 책장의 높이는 모든 개별 선반 높이의 합이다.
정올도서관의 도서관장을 위하여 책장의 최소 높이를 계산하는 프로그램을 작성하자.
입력
첫 줄에 N과 L이 입력된다. (1 ≤ N ≤ 100,000, 1 ≤ L ≤ 1,000,000,000)
두 번째 줄부터 N줄에 걸쳐 Hi와 Wi가 입력된다. (1 ≤ Hi ≤ 1,000,000, 1 ≤ Wi ≤ L)
출력
책장의 최소 높이를 출력하시오.
예제
5 10
5 7
9 2
8 5
13 2
3 8
21
총 다섯 권의 책이 있고, 각 선반은 최대 너비 10까지 책을 담을 수 있다.
그럼 총 3개의 선반이 아래와 같이 이루어져 책장의 총 높이는 21이 된다.
1: 1번 책 (높이 5, 너비 7)
2: 2,3,4번 책 (높이 13, 너비 9)
3: 5번 책(높이 3, 너비 8)
로그인해야 코드를 작성할 수 있어요.