Delicious Apples

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 ith 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≤n,k≤10⁵,ai≥1,a1+a2+...+an≤10⁵
1≤L≤10⁹
0≤x[i]≤L

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

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 total distance in a line for each testcase.