Up the Stairs

John is moving to the penthouse of a tall skyscraper. He packed all of his belongings into boxes and brought them to the entrance of the building on the ground floor. Unfortunately the elevator is out of order, so the boxes have to be carried up the stairs.

Luckily John has many friends who want to help carry his boxes up. They all walk the stairway at the same speed of 1 floor per minute, whether or not they are carrying a box. The stairway, however, is so narrow that two people cannot pass each other on it. Therefore they decided on the following rule: someone holding a box always moves up, and someone empty-handed always moves down. When two people meet somewhere on the stairway, the lower one (holding a box) hands it to the higher one (empty-handed); then the lower one walks down again and the higher one walks up. Passing a box takes no time. When someone reaches the ground floor, they pick up a box and start walking up. When someone reaches the penthouse, they drop the box and walk down again.

After a while the people are scattered across the stairway, some carrying boxes and some empty-handed. There are still a number of boxes on the ground floor, and John wonders how much more time it will take before all the boxes are up. Help him find out!

The first line contains a positive integer: the number of test cases. Then, for each test case:

• One line with three integers $N$, $F$, $B$ ($1 \le N, F \le 1000$, $1 \le B \le 1000000$): the number of people, the number of floors ($0$ = ground floor, $F$ = penthouse), and the number of boxes still on the ground floor.
• $N$ lines, each with two integers $f_i$ and $b_i$ ($0 \le f_i \le F$, $b_i$ is 0 or 1): the floor where each person initially stands and whether they are holding a box (1 = holding a box, 0 = empty-handed).

Output on one line the time, in minutes, it will take to get all of the remaining boxes to the penthouse.