Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

No tag edit access

B. Martian Architecture

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputChris the Rabbit found the traces of an ancient Martian civilization. The brave astronomer managed to see through a small telescope an architecture masterpiece — "A Road to the Sun". The building stands on cubical stones of the same size. The foundation divides the entire "road" into cells, into which the cubical stones are fit tightly. Thus, to any cell of the foundation a coordinate can be assigned. To become the leader of the tribe, a Martian should build a Road to the Sun, that is to build from those cubical stones on a given foundation a stairway. The stairway should be described by the number of stones in the initial coordinate and the coordinates of the stairway's beginning and end. Each following cell in the coordinate's increasing order should contain one cubical stone more than the previous one. At that if the cell has already got stones, they do not count in this building process, the stairways were simply built on them. In other words, let us assume that a stairway is built with the initial coordinate of *l*, the final coordinate of *r* and the number of stones in the initial coordinate *x*. That means that *x* stones will be added in the cell *l*, *x* + 1 stones will be added in the cell *l* + 1, ..., *x* + *r* - *l* stones will be added in the cell *r*.

Chris managed to find an ancient manuscript, containing the descriptions of all the stairways. Now he wants to compare the data to be sure that he has really found "A Road to the Sun". For that he chose some road cells and counted the total number of cubical stones that has been accumulated throughout the Martian history and then asked you to count using the manuscript to what the sum should ideally total.

Input

The first line contains three space-separated integers: *n*, *m*, *k* (1 ≤ *n*, *m* ≤ 10^{5}, 1 ≤ *k* ≤ *min*(*n*, 100)) which is the number of cells, the number of "Roads to the Sun" and the number of cells in the query correspondingly. Each of the following *m* roads contain three space-separated integers: *a*_{i}, *b*_{i}, *c*_{i} (1 ≤ *a*_{i} ≤ *b*_{i} ≤ *n*, 1 ≤ *c*_{i} ≤ 1000) which are the stairway's description, its beginning, end and the initial cell's height. Then follow a line, containing *k* different space-separated integers *b*_{i}. All these numbers ranging from 1 to *n* are cells, the number of stones in which interests Chris.

Output

You have to print a single number on a single line which is the sum of stones in all the cells Chris is interested in.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Examples

Input

5 2 1

1 5 1

2 4 1

3

Output

5

Input

3 2 1

1 3 1

1 3 1

2

Output

4

Input

3 2 1

1 3 1

1 3 1

3

Output

6

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/20/2017 10:51:55 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|