레이팅 미적용설명
농부 존(Farmer John)은 소젖을 짜거나, 건초 더미를 쌓거나, 소들을 줄 세우거나, 울타리를 치지 않을 때면 좋은 책과 함께 앉아 있는 것을 즐긴다. 여러 해 동안 존은 N권 (1 <= N <= 100,000)의 책을 모았고, 이제 이 책들을 모두 꽂을 새 책장을 만들고 싶어 한다.
각 책 i는 너비 W(i)와 높이 H(i)를 가진다. 책들은 순서대로 선반들에 꽂아야 한다. 예를 들어 첫 번째 선반에는 어떤 k에 대해 책 1...k가 꽂히고, 두 번째 선반은 책 k+1부터 시작하는 식이다. 각 선반의 총 너비는 최대 L (1 <= L <= 1,000,000,000)일 수 있다. 선반의 높이는 그 선반에서 가장 높은 책의 높이와 같고, 선반들은 모두 수직으로 쌓이므로 책장 전체의 높이는 각 선반의 높이의 합이다.
책장 전체의 가능한 최소 높이를 계산하는 것을 FJ에게 도와주자.
제약
입력 형식
첫째 줄: 공백으로 구분된 두 정수 N과 L.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 공백으로 구분된 두 정수 H(i)와 W(i)가 주어진다. (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
출력 형식
책장 전체의 가능한 최소 총 높이.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
bookshelf.in · 출력을 쓸 파일 bookshelf.out예제 1
입력
5 10
5 7
9 2
8 5
13 2
3 8출력
21설명
Output details: There are 3 shelves, the first containing just book 1, the second containing books 2..4, and the third containing book 5.
문제 정보
태그