E. Connecting Buildings
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Confused by MIT's building layout, Busy Beaver decided to design a simpler layout – the Majestic Interconnected Toroid Institute of Technology (MITIT)...

There are $$$N$$$ main buildings numbered $$$1,\dots,N$$$ arranged on a circle with circumference $$$C$$$. The $$$i$$$th building is located at position $$$L_i$$$ ($$$0 \le L_i \lt C$$$) along the circle and has a height of $$$H_i$$$. There is one more building, the student center, located at the center of the circle whose height is not decided yet.

Busy Beaver wants to connect the $$$N+1$$$ buildings with some straight tunnels such that any building can reach any other building using these tunnels. A tunnel can be modeled as a line segment (in a 2-dimensional plane) connecting two of the buildings. All these tunnels will be at the same elevation, so their corresponding line segments must not intersect (except at endpoints). For some reason, the cost of constructing a tunnel between two buildings with heights $$$h_1$$$ and $$$h_2$$$ is equal to $$$|h_1-h_2|$$$.

Busy Beaver has $$$Q$$$ questions $$$M_1,\dots,M_Q$$$, where he wonders: What is the minimum possible cost to connect all the buildings if the student center has a height of $$$M_i$$$?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 500$$$). The description of the test cases follows.

The first line of each test case contains three integers, $$$N$$$, $$$Q$$$, and $$$C$$$ ($$$1 \le N \le 500$$$, $$$1 \le Q \le 10^6$$$, $$$1 \le C \le 10^9$$$).

The $$$i^\text{th}$$$ of the next $$$N$$$ lines contains two integers $$$L_i$$$ and $$$H_i$$$ ($$$0 \le L_i \lt C$$$, $$$1 \le H_i \le 10^9$$$).

The $$$i^\text{th}$$$ of the next $$$Q$$$ lines contains a single integer $$$M_i$$$ ($$$1 \le M_i \le 10^9$$$).

The $$$L_i$$$ are pairwise distinct and there does not exist two diametrically opposite buildings ($$$i$$$ and $$$j$$$ such that $$$L_i = L_j+C/2$$$).

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$500$$$.

It is guaranteed that the sum of $$$Q$$$ over all test cases does not exceed $$$10^6$$$.

Output

Output $$$Q$$$ lines: the minimum cost to connect all the buildings when the student center has a height of $$$M_1,\dots,M_Q$$$ respectively.

Scoring

Let $$$\sum N$$$ denote the sum of $$$N$$$ over all test cases and $$$\sum Q$$$ denote the sum of $$$Q$$$ over all test cases.

  • ($$$15$$$ points) $$$\sum N,\sum Q \le 80$$$ and $$$0 \le L_i \lt C/2$$$ for all $$$i$$$.
  • ($$$15$$$ points) $$$\sum N,\sum Q \le 80$$$.
  • ($$$15$$$ points) $$$\sum N \le 80$$$ and $$$0 \le L_i \lt C/2$$$ for all $$$i$$$.
  • ($$$10$$$ points) $$$\sum N \le 80$$$.
  • ($$$15$$$ points) $$$\sum Q \le 500$$$ and $$$0 \le L_i \lt C/2$$$ for all $$$i$$$.
  • ($$$10$$$ points) $$$\sum Q \le 500$$$.
  • ($$$10$$$ points) $$$0 \le L_i \lt C/2$$$ for all $$$i$$$.
  • ($$$10$$$ points) No additional constraints.
Example
Input
2
4 4 5
0 3
1 1
2 4
4 1
5
9
2
6
1 1 1000000000
998244353 998244353
1
Output
6
10
5
7
998244352
Note

One optimal way to connect the buildings for the questions in the first test case are as shown:

For the second test case, the cost to connect the student center with the only other building is $$$|1-998244353| = 998244352$$$.