Delicious Apples

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.

Sample Input

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

Sample Output

18
26

Author

XJZX

Source

2015 Multi-University Training Contest 2