Optimal Bookshelf Arrangement

You are given (N) books which must be placed on a bookshelf in the given order. Each book (i) has a width (w_i) and height (h_i). Books are arranged in shelves, and each shelf can contain a contiguous sequence of books such that the total width of the books on that shelf does not exceed a maximum width (W). The height of a shelf is defined as the maximum height of the books on that shelf. Your task is to determine the minimum possible total height of the bookshelf when the books are arranged optimally into shelves. (\textbf{Formally,}) if a shelf contains books (j, j+1, \dots, i) then the shelf is valid if (\sum_{k=j}^{i} w_k \le W) and its height is (\max_{k=j}^{i} h_k). Minimize the sum of the heights of all shelves.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer (N), representing the number of books. Each of the next (N) lines contains two integers (w_i) and (h_i) (the width and the height of the (i)-th book). The last line contains the integer (W), the maximum allowable width of each shelf.

outputFormat

Output a single integer which is the minimum total height of the bookshelf arrangement, written to standard output (stdout).## sample

4
1 3
2 4
3 2
1 6
5

10