Bong Joon-gu is a gardener,he is always active and never lazy.He maintained a garden in the shape of polygon having 'N' vertices and perimeter 'P'.There is a plant on each vertex. There are f[i] number of flowers on ith plant(clockwise).

Bong has his house in between 1st and nth vertex of garden and ith plant is located at the distance d[i] meters from the house (clockwise).

He has carry trolley having capacity of 'K' flowers.He can either go clockwise to 2nd vertex or counter-clockwise to nth vertex.He can run at constant speed of 1 m/s.

He starts from his house,pluck all the flowers and bring them back to his house using his trolley.

Bong asked you to tell what is the minimum time required to pluck all flowers.

Assumption : He plucks flower in zero time.

Input :

First Line contains an integer 'T' indicating number of test cases. Next line contains three integers 'P','N','K' indicating perimeter of garden, number of plants, capacity of trolley. Next 'N' lines contains d[i] and f[i] indicating distance of ith plant from house in clockwise direction and number of flowers on ith plant.

Output :

For each testcase, Output minimum time to pluck all flowers in seconds.

Constraints :

1 <= T <= 1000

1 <= N , K <= 105

1 <= P <= 109

0 <= d[i] <= P

f[1] + f[2] + ... + f[n] <= 105 , f[i] >= 1