책장

찰스는 생일 선물로 많은 책을 받아, 이 책들을 보관할 책장을 만들기로 했다. 작은 집에서 책장을 놓을 수 있는 유일한 공간은 문 옆의 빈자리뿐이므로, 책장의 너비는 그 빈 공간의 크기로 고정되어 있다. 또한 찰스는 책장 맨 위에 화분을 올려 두고 싶어 한다. 키가 크지 않은 그는 물을 줄 때마다 사다리를 쓰지 않도록 책장을 가능한 한 낮게 만들고 싶어 한다. 물론 자신의 책이 모두 책장 안에 들어가야 한다.

각 칸(선반)에서 찰스는 책을 두 가지 방식으로 놓으며, 한 칸 안에서 왼쪽에서 오른쪽으로 두 방식을 섞어 쓸 수도 있다.

• 세워 놓기(수직): 책을 똑바로 세운다. 이때 가로로 차지하는 폭은 책의 두께 $w$, 세로 높이는 책의 높이 $h$이다.
• 눕혀 쌓기(수평 기둥): 연속한 한 권 이상의 책을 눕혀 위로 차곡차곡 쌓는다. 이렇게 만든 기둥이 가로로 차지하는 폭은 그 안에 있는 책들의 높이 $h$ 중 최댓값이고, 세로 높이는 그 책들의 두께 $w$의 합이다.

찰스는 꼼꼼한 사서이므로 책은 어디에서나 알파벳 순서를 지킨다. 즉 위 칸에서 아래 칸으로, 한 칸 안에서는 왼쪽에서 오른쪽으로, 기둥 안에서는 위에서 아래로 순서가 이어진다.

책장은 칸을 위로 쌓아 만든다. 모든 칸은 두께 1 cm(10 mm)짜리 판 위에 놓이고, 맨 위에는 화분을 받치기 위한 판 하나가 1 cm(10 mm) 더 얹힌다. 판을 제외한 한 칸의 높이는 1 m(1000 mm)를 넘을 수 없다.

모든 책의 크기와 책장의 너비가 주어질 때, 책장의 가능한 최소 높이를 구하여라.

첫째 줄에 책의 수 $N$ ($1 \le N \le 1000$)이 주어진다. 이어지는 $N$개의 줄에는 각각 한 권의 책의 높이 $h$와 두께 $w$ ($1 \le h, w \le 1000$)가 공백으로 구분되어 주어진다. 마지막 줄에는 책장의 너비 $W$ ($1 \le W \le 10000$)가 주어진다. 모든 크기는 밀리미터 단위의 정수이며, 책은 알파벳 순서로 나열되어 있다.

책장의 최소 높이 $H$를 밀리미터 단위의 정수 하나로 출력한다.

첫 번째 예제에서 최적의 책장은 칸이 두 개다. 아래 칸에는 책 한 권을 눕혀 한 권짜리 기둥으로 놓고, 위 칸에는 나머지 네 권을 나란히 세워 놓는다. 위 칸 위에는 화분을 받치는 판이 놓인다.