Pizza

Time limit2sMemory limit128 MB

Summary

Given store positions on a circular road and delivery points, sum the distance from each point to its nearest store.

Level: Medium4 of 10
Topics: Binary search, Array, Sorting
Solved: No attempts yet

Problem

JOI Pizza delivers pizzas along a ring road of total length $d$ meters that runs through the center of the city.

JOI Pizza has $n$ stores $S_1, \dots, S_n$ on the ring road; the main store is $S_1$ . Let $d_i$ be the distance, in meters, traveled clockwise along the ring road from $S_1$ to $S_i$ . Each of $d_2, \dots, d_n$ is an integer between $1$ and $d-1$ , and they are all distinct.

When an order arrives, the pizza is baked and delivered from the store whose travel distance to the delivery location is smallest, so that the pizza does not get cold.

A delivery location is given by an integer $k$ with $0 \le k \le d-1$ : it is the point reached by traveling $k$ meters clockwise along the ring road from the main store $S_1$ . Deliveries must follow the ring road and no other route is allowed, but you may travel either clockwise or counterclockwise. Hence the distance from a store to a delivery location is the shorter of the two arc lengths between them.

For example, suppose the stores and delivery locations are arranged as in the figure below.

The store nearest the first delivery location is $S_2$ , so it is delivered from $S_2$ ; the travel distance from that store is $1$ . The store nearest the second delivery location is the main store $S_1$ , so it is delivered from $S_1$ ; the travel distance is $2$ .

Given the total length $d$ of the ring road, the number of stores $n$ , the number of orders $m$ , the $n-1$ integers $d_2, \dots, d_n$ giving the positions of the stores other than the main store, and the integers $k_1, \dots, k_m$ giving the delivery locations, write a program that computes the sum, over all orders, of the delivery travel distance (the distance from the nearest store to the delivery location).

Input

The input is given in the following format.

Line 1: an integer $d$ , the total length of the ring road ( $2 \le d \le 10^9$ ).
Line 2: an integer $n$ , the number of stores ( $2 \le n \le 100000$ ).
Line 3: an integer $m$ , the number of orders ( $1 \le m \le 10000$ ).
The next $n-1$ lines: the positions $d_2, d_3, \dots, d_n$ ( $1 \le d_i \le d-1$ ) of the stores other than the main store, one per line in this order. These values are all distinct.
The following $m$ lines: the delivery locations $k_1, k_2, \dots, k_m$ ( $0 \le k_i \le d-1$ ), one per line in this order.

Output

Output a single integer on one line: the sum of the delivery travel distances.

Examples5

Example 1
Input
```
8
3
2
3
1
4
6
```
Expected output
```
3
```
Example 2
Input
```
20
4
4
12
8
16
7
7
11
8
```
Expected output
```
3
```
Example 3
Input
```
2
2
1
1
0
```
Expected output
```
0
```
Example 4
Input
```
10
3
3
4
7
0
5
9
```
Expected output
```
2
```
Example 5
Input
```
100
2
2
50
99
1
```
Expected output
```
2
```