다시 보는 워드 클라우드

태그 존슨은 워드 클라우드를 그리는 소프트웨어를 만든다. 워드 클라우드는 글 데이터를 그림으로 나타낸 것으로, 각 단어를 감싸는 상자의 크기는 그 단어가 원문에 나오는 상대 빈도에 따라 정해진다.

태그는 항목을 줄 단위로 배치하는 알고리즘에서 이상한 점을 발견했다. 워드 클라우드에는 최대 너비가 정해져 있고, 태그는 전체 높이를 가장 작게 만들고 싶다. 항목은 정해진 순서대로 놓아야 한다. 각 항목은 바로 앞 항목의 오른쪽에 같은 줄로 이어 붙이거나, 새 줄의 맨 왼쪽에 놓는다. 한 줄의 높이는 그 줄에 놓인 항목 높이의 최댓값이고, 클라우드의 전체 높이는 각 줄 높이의 합이다.

태그가 처음 만든 알고리즘은 너비 제한 때문에 들어가지 않는 경우가 아니면 항목을 앞 항목과 같은 줄에 놓는다. 그림 1은 최대 너비가 260인 어떤 클라우드에 이 알고리즘을 적용한 결과다.

그림 1: 태그가 처음 만든 알고리즘의 배치

첫째 줄에는 앞의 세 항목이 들어가고 너비 합은 238이다. 넷째와 다섯째 항목이 둘째 줄을 함께 쓰고 너비 합은 193이다. 여섯째 항목은 마지막 줄에 혼자 놓인다. 세 줄의 높이는 각각 48, 43, 23이므로 클라우드의 높이는 $48 + 43 + 23 = 114$이다.

태그는 나중에 같은 자료로 더 나은 클라우드를 만들 수 있다는 것을 알았고, 그 결과가 그림 2다. 첫째와 둘째 항목을 한 줄에, 셋째와 넷째 항목을 다음 줄에, 다섯째와 여섯째 항목을 그다음 줄에 놓으면 너비 제한 260을 지키면서도 전체 높이가 $23 + 48 + 28 = 99$까지 줄어든다.

그림 2: 그림 1의 항목을 최적으로 배치한 결과

항목 목록과 최대 너비가 주어질 때, 높이가 가장 작은 워드 클라우드를 만들어라.

첫째 줄에 정수 $N$과 $C$가 주어진다. $N$ ($2 \le N \le 5000$)은 놓아야 할 항목의 개수이고, $C$ ($150 \le C \le 1000$)는 클라우드의 최대 너비다.

다음 $N$개 줄에 각각 정수 $w$와 $h$ ($10 \le w \le 150$, $10 \le h \le 150$)가 주어진다. 이는 항목 하나의 너비와 높이이며, 배치해야 하는 순서대로 주어진다.

위 규칙을 지키면서 워드 클라우드를 만들 때 필요한 최소 높이를 출력한다.