시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 64 MB111100.000%

문제

Charles got a heap of books on his birthday and he decided to make a book-case for their storage. He found a place (maybe the last possible one) for it in his small flat – he has some space next to the door. Charles would like to have some houseplants on the top the book-case. However, he isn’t very tall, so he would like to build a book-case of the least possible height to avoid having to use a stepladder for every watering of the plants. The width of the book-case is a given constant, it is the width of the free space next to the door. And of course Charles wants all his books to fit into the book-case.

When Charles puts the books into the shelves of his book-case, he uses two different ways: vertically one next to another, or into a column (horizontally) one over another. And he can combine these two ways in a single shelf: he can begin placing the books vertically, then make a column, then again vertically. . .(in both cases he makes the spines of the book visible). And because Charles is a pedant (and maybe also thanks to his librarian profession), he places the books according to their alphabetic order: from the top shelf to the bottom shelf, on every shelf from the left to the right and in a column from the top to the bottom.

He nearly wanted to set out to buy the needed material when he realised that the optimization of height of the new book-case isn’t so simple as he thought. So he began writing a program, which could help him with this difficult work. Charles knows the height and the width of the spine of each book, the desired width of the library. He also knows that has to add 1 cm for the board of each shelf and another 1 cm for the top board (the one which will carry the flower pots). Each shelf can be at most 1 m high, excluding the boards.

Help Charles and find the minimal possible height of the book-case.

입력

The first line of the input contains a single number N (1 ≤ N ≤ 1 000), the number of books. The following N lines describe the books. Each of them contains two numbers h and w separated by a single space (1 ≤ h, w ≤ 1 000), where h is the height and w is the width of the book. The last line in the file consists of one number W (1 ≤ W ≤ 10 000), which is the desired width of the whole book-case. The sizes of books and the width of the book-case are given in milimeters as whole numbers. The books are listed in alphabetical order.

출력

The output should contain a single number H – the minimal possible height of the book-case (in milimeters).

예제 입력 1

5
300 160
300 160
300 160
300 160
900 90
1000

예제 출력 1

420

힌트

(The book-case will contain two shelves. On the bottom one, there will be a column consisting of a single book. The top one will hold the remaining four books placed vertically. And above that, there will be the board with the flowers.)