“Hurray! We finally destroyed the red stone system!” Blues bounces up and down.
Then he sees Pinky’s body going stiff. “Pinky, I will live for you!” He yells, but all that answers him are his own echoes.
“Little Graphy, let’s go!” Blues stands up, wipes his tears, and walks toward the exit.
Little Graphy keeps up with Blues, and soon she finds a chest filled with some potions. “Oh, the splash potion of harming 2! It may be a great weapon!” she thinks.
Outside the cavern, they find a guy going against a lot of monsters.
He says, “My name is Big China Day. Can you please help me defeat the little pets from the Black Dark Witch?”
Little Graphy looks around, and finds that there are N monsters surrounding them. Monster i has a HP (Health point) Hi. If a monster’s HP goes down to 0, it will die.
Little Graphy has M splash potions of harming 2, and each potion can cause 1 HP of damage on one monster. Big China Day has a magic energy gun which can nerf monsters. That is to say, if the monster i is shot, his HP will become Ci (Ci ≤ Hi). Then it will be easily defeated. However, you can’t shoot at the same monster twice!
The magic energy gun can shoot at most K times, and Little Graphy wants to know how many monsters they can kill with the best strategy.
The first line contains an integer T indicating the number of test cases.
Each test case begins with N, K, M.
The following N lines contain two integers Hi, Ci.
For each test case, print a single line containing a non-negative integer which means the maximum number of monsters they can kill.