Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3320
Break Out

Time Limit: 10 Seconds      Memory Limit: 32768 KB

The game "Bricks" is to use left and right keys to control the paddle so that the ball cannot fall out of the window. If the ball falls out of the window, your lives will decrease. Your job is to break all the bricks with the ball before your lives fall to zero. The bricks have different colors and different values. Some of the bricks will drop some special awards that can slow down the ball, split the ball into two or give some special effects to the ball or to the paddle. Collecting the awards may make it easier to win.

Navi likes playing this game very much. But he has some difficulty in playing the game while he reaches the level that has two paddles. He can control the ball so well that he can hit any brick he wants. However, when an award is dropped, he always collects the award first and forgets to catch the ball. He managed to hack the game so that he could get the map of the bricks, but he still could not finish the game. Poor Navi! If you can help Navi finish the game, you will be awarded by him. Anyway, given the map of bricks, your task here is to calculate the maximum points that Navi can get.

To simplify the problem, here we make some assumptions. A brick is broken if all the bricks in the direction the ball is coming are broken. That is to say, it can be broken if all bricks below it are broken and the ball is coming from below, or all bricks above it are broken and the ball is coming from above. At first, the ball is placed below all the bricks. It cannot fly over the bricks until at least one column of bricks are broken.

Input

There are no more than 50 test cases. The first line of each test case contains two integers N and M, indicating the size of the map (1 <= N, M <= 200). Then N rows of M bricks are described in the next N lines. Each brick is described with two integers v and d. The bricks are described from up to down. v is the value of the brick (1 <= v <= 50000). d equals 1 if after this brick is broken, an award is drop. Otherwise, d equals 0. All the integers are separated by one space. The last line of each test cases contains one integer L, indicating the initial lives of the game (1 <= L <= 200).

Two zeroes indicate the end of the input, which should not be processed.

Output

For each test case, output the maximum points that Navi can get.

Sample Input

2 2
10 1 20 1
1 1 2 1
1
2 2
10 1 20 1
1 1 2 0
2
0 0

Sample Output

2
32


Author: GUAN, Yao
Source: The 10th Zhejiang University Programming Contest
Submit    Status