JOI '14 Open P2 - Fortune Telling 2

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types
Contest Day 1 - JOI Open Contest

Prof. K is the President of the Japanese Committee for the International Olympiad in Informatics. He loves fortune-telling. He is always doing several kinds of fortune-tellings. Today, he decided to do a fortune-telling using cards to see the results of the Japanese delegation of this year's IOI.
An integer is written on each side of each card. Integers on both sides of a card are not necessarily equal. If you put a card on a table so that you can see the integer on one side, you cannot see the integer on the other side.
The fortune-telling is done as follows.

  • First, Prof. K will put N cards on a table. The cards are numbered from 1 to N. The integer A_i is written on one side of the card i, and the integer B_i is written on the other side of the card i. He will put the cards on the table so that A_i is shown on the card i for each i.
  • For j = 1,\dots,K, he will do the following operation: "If the integer shown on each card is less than or equal to T_j, he will turn it upside down."
  • The result of the fortune-telling is the sum of the integers shown on the cards on the table after these K operations are finished.

At some point, Prof. K realized that deciding which cards are to be turned upside down is a boring job. He finally gave up doing the fortune-telling by using the cards. He only wants to know the sum of the integers shown on the cards on the table after these K operations are finished.

Task

Write a program which, given the integers written on the cards and the information of the operations, calculates the sum of the integers shown on the cards on the table after all operations are finished.

Input

Read the following data from the standard input.

  • The first line contains two space separated integers N and K. This means there are N cards and the number of operations is K.
  • The i^{th} line (1 \le i \le N) of the following N lines contains two space separated integers A_i and B_i. This means the integers written on the card i are A_i and B_i.
  • The j^{th} line (1 \le j \le K) of the following K lines contains an integer T_j. This means, in the j^{th} operation, if the integer shown on a card is less than or equal to T_j, it will be turned upside down.

Output

To the standard output, write the sum of the integers shown on the cards on the table after K operations are finished.

Constraints

All input data satisfy the following conditions:

  • 1 \le N \le 200\,000.
  • 1 \le K \le 200\,000.
  • 1 \le A_i \le 1\,000\,000\,000 (1 \le i \le N).
  • 1 \le B_i \le 1\,000\,000\,000 (1 \le i \le N).
  • 1 \le T_j \le 1\,000\,000\,000 (1 \le j \le K).

Subtask 1 [4 points]

The following conditions are satisfied:

  • N \le 1\,000
  • K \le 1\,000

Subtask 2 [31 points]

The following conditions are satisfied:

  • N \le 40\,000
  • K \le 40\,000

Subtask 3 [65 points]

No additional constraints.

Sample Input

5 3
4 6
9 1
8 8
4 2
3 7
8
2
9

Sample Output

18

Explanation of Output for Sample Input

First, the five integers shown on the cards are 4, 9, 8, 4, 3, respectively. The operations are done as follows.

  • If the integer shown on each card is less than or equal to 8, it will be turned upside down. After the operation, the integers shown on the cards are 6, 9, 8, 2, 7, respectively.
  • If the integer shown on each card is less than or equal to 2, it will be turned upside down. After the operation, the integers shown on the cards are 6, 9, 8, 4, 7, respectively.
  • If the integer shown on each card is less than or equal to 9, it will be turned upside down. After the operation, the integers shown on the cards are 4, 1, 8, 2, 3, respectively.

After all operations are finished, the sum of the integers shown on the cards on the table is 4+1+8+2+3=18.


Comments

There are no comments at the moment.