레이팅 미적용농부 존(Farmer John)은 소젖을 짜거나, 건초 더미를 쌓거나, 소들을 줄 세우거나, 울타리를 치지 않을 때면 좋은 책과 함께 앉아 있는 것을 즐긴다. 여러 해 동안 존은 N권 (1 <= N <= 2,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).
책장 전체의 가능한 최소 총 높이.
bookshelf.in · 출력을 쓸 파일 bookshelf.out5 10
5 7
9 2
8 5
13 2
3 821Output details: There are 3 shelves, the first containing just book 1 (height 5, width 7), the second containing books 2..4 (height 13, width 9), and the third containing book 5 (height 3, width 8).
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > US Open > Silver