Street Tree Props (Large)

You were elected mayor of city G. As part of a beautification program you decide to plant street trees along the roads. Only after buying the trees do you learn that a young tree needs props to grow straight.

You want to know whether the wooden sticks you already own can prop up every tree you bought. The rules are these.

• Every tree has to be propped up. None may be left out.
• Each tree needs the same supporting force $B$.
• To prop a tree you stand a stick against it, and that stick's supporting force has to be at least $B$.
• Sticks with the same supporting force are grouped into one kind, and you know how many sticks each kind holds.
• For the sake of appearance a tree takes at most two props. Two sticks hold the tree with the sum of their supporting forces, so that sum has to be at least $B$.
• One stick props at most one tree, and a stick may be left unused.
• Among the ways that satisfy every rule above, minimize the total supporting force of the sticks you use.

The variables are defined as follows.

• $T$ = number of test cases
• $N$ = number of trees
• $B$ = supporting force one tree needs (the same for every tree)
• $M$ = number of stick kinds
• $p_i$ = supporting force of one stick of the $i$-th kind
• $q_i$ = number of sticks of the $i$-th kind

The input has this format.

T
N M B
p1 q1
p2 q2
...
pM qM

The first line holds $T$. Then $T$ test cases follow. The first line of a test case holds $N$, $M$ and $B$ separated by spaces, and each of the next $M$ lines holds $p_i$ and $q_i$.

Limits

• Every input value is an integer.
• $1 \le T \le 50$
• $1 \le N \le 100000$
• $1 \le M \le 1000$
• $1 \le B \le 10000$
• $1 \le p_i \le 20000$
• $1 \le q_i \le 200000$

For each test case print one line in the form Case #x: y, where $x$ is the test case number starting from 1. If every street tree can be propped up, $y$ is the smallest possible total supporting force of the sticks used. Otherwise $y$ is -1.