Book-case

Charles received a large pile of books for his birthday and decided to build a book-case to store them. The only free spot in his small flat is the space next to a door, so the width of the book-case is fixed and equal to that free space. Charles also wants to keep some flower pots on the very top of the book-case; since he is not tall, he wants the book-case to be as low as possible so he does not need a stepladder every time he waters the plants. Of course, all of his books must fit inside.

On each shelf Charles arranges books in one of two ways, and he may mix both ways on the same shelf, going from left to right:

• Standing (vertical): a book stands upright, occupying a width equal to its thickness $w$ and a height equal to its height $h$.
• Column (lying): one or more consecutive books are laid flat and stacked one on top of another. Such a column occupies a width equal to the largest height $h$ among its books and a height equal to the sum of the thicknesses $w$ of its books.

Because Charles is a meticulous librarian, the books keep their alphabetical order everywhere: from the top shelf to the bottom shelf, on each shelf from left to right, and within a column from top to bottom.

The book-case is built from shelves stacked on top of one another. Every shelf rests on a board that adds 1 cm (10 mm) of height, and one extra board of 1 cm (10 mm) is placed on the very top to carry the flower pots. Excluding the boards, no single shelf may be taller than 1 m (1000 mm).

Given the size of every book and the required width of the book-case, compute the minimum possible height of the book-case.

The first line contains a single integer $N$ ($1 \le N \le 1000$), the number of books. Each of the next $N$ lines contains two integers $h$ and $w$ ($1 \le h, w \le 1000$), the height and the thickness of one book. The last line contains a single integer $W$ ($1 \le W \le 10000$), the required width of the book-case. All sizes are given in millimeters, and the books are listed in alphabetical order.

Print a single integer $H$: the minimum possible height of the book-case, in millimeters.

In the first example the optimal book-case has two shelves. The bottom shelf holds one book laid flat as a column of a single book; the top shelf holds the remaining four books standing side by side. Above the top shelf sits the board that carries the flower pots.