Street Tree Props (Small)

You were elected mayor of city G. As part of a beautification project you decided to plant street trees along the road, and only after buying the trees did you learn that a tree needs a prop to grow properly.

You want to know whether the wooden sticks you already own are enough to prop up every tree you bought. The conditions are below.

• Every tree must be supported.
• You know the support each tree needs and the support each stick provides. Every tree needs the same support $B$.
• A tree is propped up with wooden sticks. If only one stick is used, its support must be at least $B$.
• Sticks with the same support are grouped into one type, and the count of each type is known. One stick can be used for at most one tree.
• This is a beautification project, so a tree may use at most 2 props. When two sticks are used, they hold the tree with the sum of their supports.

Among all ways that satisfy the conditions above, minimize the total support of the sticks you use.

Define the variables as follows.

• $T$ = the number of test cases
• $N$ = the number of trees
• $B$ = the support one tree needs (the same for every tree)
• $M$ = the number of stick types
• $p_i$ = the support provided by a stick of the $i$-th type
• $q_i$ = the number of sticks of the $i$-th type

The first line holds $T$, and $T$ test cases follow. Each test case has this format.

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

Limits

• Every input value is an integer.
• $1 \le T \le 50$
• $1 \le N \le 10$
• $1 \le M \le 10$
• $1 \le B \le 1000$
• $1 \le p_i \le 2000$
• $1 \le q_i \le 20$

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