Problem Description

There are $n$ apple trees planted along a cyclic road, which is $L$ metres long. Your storehouse is built at position $0$ on that cyclic road.
The $i$th tree is planted at position $x_i$, clockwise from position $0$. There are $a_i$ delicious apple(s) on the $i$th tree.

You only have a basket which can contain at most $K$ apple(s). You are to start from your storehouse, pick all the apples and carry them back to your storehouse using your basket. What is your minimum distance travelled?

$1\le n,k\le 10^5, a_i\ge 1, a_1+a_2+...+a_n\le 10^5$
$1\le L\le 10^9$
$0\le x[i]\le L$

There are less than 20 huge testcases, and less than 500 small testcases.

Input

First line: $t$, the number of testcases.
Then $t$ testcases follow. In each testcase:
First line contains three integers, $L,n,K$.
Next $n$ lines, each line contains $x_i,a_i$.

Output

Output total distance in a line for each testcase.

2
10 3 2
2 2
8 2
5 1
10 4 1
2 2
8 2
5 1
0 10000

18
26

Author

XJZX