Problem Background

NOIP2018 Original Mock Test T5

NOIP2018 Original Mock Competition DAY2 T1

NOIP T1+ or T2- Difficulty Level

Adapted from the novel "Harry Potter and the Deathly Hallows"

Problem Description

The final battle has begun.

Harry has been declared "dead," and Voldemort is preparing to attack Hogwarts with his followers. However, Hogwarts is protected by ancient magic, which they must first destroy. There are $n$ layers of protection, each with two parameters: $k$ and $p$. $k$ represents the type of magic, and $p$ represents the magnitude of the energy.

Each second, Voldemort penetrates one layer of protection. At the $i$-th second (having reached the $i$-th layer), he has the following options:

1. Collect the magical energy of type $x_i$ from layers $[1, i]$.
2. Collect the magical energy from the layer with the maximum energy within layers $[1, i]$.
3. Use a doubling spell.

For each of these choices, he can select one per second and may gain energy. The amount of energy gained varies by choice:

• For option 1, he gains the total magical energy of type $x_i$ from layers $[1, i]$ (refer to Sample 1 for understanding).
• For option 2, he gains the magical energy from the layer with the highest energy within layers $[1, i]$.
• For option 3, the energy collected this second remains unchanged (i.e., no new energy is collected), but the energy gained next second is doubled. However, he cannot use the doubling spell consecutively, and he can use it at most $m$ times. He can repeatedly collect energy from each layer.

Only by passing through these $n$ layers and acquiring the maximum magical energy can he completely destroy Hogwarts' magical defenses. However, wizards are not adept at calculations.

Thus, Voldemort has turned to you, a Muggle programmer skilled in computer technology. Your task is to design a program to help Voldemort calculate the maximum magical energy he can obtain.

The final battle is underway, and the history of the magical world turns another page...

Input Format

The first line contains two numbers: $n$ and $m$, as described in the problem.

The next $n$ lines, the $(i+1)$-th line represents $k_i$ and $p_i$, as described in the problem.

The last line contains $n$ numbers, the $i$-th number represents $x_i$, as described in the problem.

Output Format

A single number representing the maximum energy value Voldemort can obtain.

Sample Input and Output

Input Sample #1

4 1
1 2
2 3
1 2
3 8
3 2 1 3

Output Sample #1

21

Input Sample #2

8 3
1 2
2 5
3 2
2 3
1 4
1 6
2 2
3 3
1 3 2 1 4 5 2 1

Output Sample #2

57

Input Sample #3

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

Output Sample #3

124

Notes

Sample 1 Explanation:

In the first second, the maximum energy that can be obtained is 2. In the second second, the maximum energy is 3. Since in the third second, energy of type 1 can be collected, the maximum energy that can be obtained is 4. In the fourth second, the maximum energy is 8. Therefore, choosing to use the doubling spell in the third second results in a total of: $2 + 3 + 0 + 2 * 8 = 21$ energy.

Data Range:

30% of the data satisfies: $n <= 100, m <= 10$

50% of the data satisfies: $n <= 5,000, m <= 20$

70% of the data satisfies: $n, m <= 2 \times 10^4, m <= 200$

100% of the data satisfies: $n <= 5 \times 10^4, m <= 500, 0 < p_i <= 10^4, 0 < k_i <= 10^9, 0 < x_i <= 10^9$

Special Conditions:

30% of the data satisfies $m = 0$

见题面 Input 部分

见题面 Output 部分