Background

NOIP 2018 original mock problem T5.

NOIP 2018 original mock contest DAY 2 T1.

NOIP T1+ or T2- difficulty.

The background is adapted from the novel Harry Potter and the Deathly Hallows.

Problem Description

The final battle has begun.

Harry is declared “dead”, and Voldemort, together with his followers, is ready to attack Hogwarts. However, Hogwarts is protected by ancient magic, and they must destroy these protections first. There are a total of $n$ layers of magical protection. Each layer has two parameters: $k, p$. Here, $k$ represents the type of magic, and $p$ represents the amount of energy.

Voldemort passes through one layer of protection per second. In the $i$-th second (when he reaches the $i$-th layer), he has the following choices:

1. Collect the magic energy of type $x_i$ among layers $[1,i]$.
2. Collect the magic energy of the layer with the maximum energy among layers $[1,i]$.
3. Use the doubling spell.

Among the three choices above, he can choose one each second, and may gain energy. Different choices yield different energy:

• For choice 1, he gains the magic energy of all layers in $[1,i]$ whose magic type is $x_i$ (please refer to Sample 1 for understanding).
• For choice 2, he gains the magic energy of the layer with the maximum energy in $[1,i]$.
• For choice 3, the total energy collected in this second does not change (that is, he does not collect new energy in this second), but the energy gained in the next second is doubled. However, he cannot use the doubling spell consecutively, and he can use it at most $m$ times. For the energy of each layer, he may collect it repeatedly.

Only if he passes through all $n$ layers of protection and obtains the maximum possible magic energy can he completely destroy Hogwarts’ magical defenses, but wizards are not good at calculations.

So, Voldemort comes to you. As a Muggle programmer skilled in computer technology, you now need to design a program to help Voldemort compute the maximum magic energy he can obtain.

The final showdown has begun, and the history of the wizarding world has turned another page.

Input Format

The first line contains two numbers: $n, m$, as described above.

The next $n$ lines: the $(i+1)$-th line contains $k_i, p_i$, as described above.

The last line contains $n$ numbers. The $i$-th number is $x_i$, as described above.

Output Format

Output one number, representing the maximum energy value Voldemort can obtain.

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

21

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

57

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

124

Hint

Explanation of Sample 1:

In the first second, he can obtain at most $2$ experience points. In the second second, he can obtain at most $3$ experience points. Because in the third second he can collect energy of magic type $1$, he can obtain at most $4$ energy. In the fourth second, he can obtain at most $8$ experience points. Therefore, choose to use the doubling spell in the third second, and the total energy obtained is $2+3+0+2*8=21$.

Constraints:

For $30\%$ of the testdata: $n<=100, m<=10$.

For $50\%$ of the testdata: $n<=5,000, m<=20$.

For $70\%$ of the testdata: $n, m<=2\times 10^4, m<=200$.

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

Special Note:

For $30\%$ of the testdata: $m=0$.

Translated by ChatGPT 5