수 십년에 걸친 노력 끝에 N권의 책을 모은 정올도서관의 도서관장은 이 책들을 보관할 책장을 만들고자 한다.

각 i번째 책에 대하여 W_i의 너비와 H_i의 높이를 가진 N권의 책들이 1부터 i번째까지 있을 때, 이 책들은 반드시 연속된 순서대로 선반에 놓여야 한다.

예를 들어, 첫 선반에 1...k 책이 있다면, 두 번째 선반은 k+1 책부터 시작하는 형식이다.

각 선반의 총 너비는 최대 L이며, 선반의 높이는 해당 선반에서 가장 높은 책의 높이와 동일하고, 전체 책장의 높이는 모든 개별 선반 높이의 합이다.

정올도서관의 도서관장을 위하여 책장의 최소 높이를 계산하는 프로그램을 작성하자.

책장 만들기 timer 1s memory 128MB

책장 만들기 1s 128MB