Problem Description

In the JOI Museum, there are $ N $ paintings displayed in a row. There are $ M $ types of paintings, numbered from $ 1 $ to $ M $. The type of the $ i $-th ($1 \leq i \leq N$) painting from the left is $ A_i $, and its value is $ V_i $. Note that $ V_i $ can be negative.

Next month, the JOI Museum is planning to host "EGOI Exhibition 2022", which is expected to attract many visitors. Therefore, the museum wants to improve the appearance by removing some paintings so that no two adjacent paintings are of the same type.

On the other hand, to enhance the reputation, they want to maximize the total value of the remaining paintings.

Given the number of paintings, the number of types, and the information of the $ N $ paintings, create a program to find the maximum possible total value of the remaining paintings.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ V_1 $ $ A_2 $ $ V_2 $ $\vdots$ $ A_N $ $ V_N $

Output Format

Output the maximum possible total value of the remaining paintings on a single line to the standard output.

Sample Input and Output

Sample Input #1

3
1
1 107
1 123
1 100

Sample Output #1

123

Sample Input #2

4
3
1 204
2 168
2 277
1 219

Sample Output #2

700

Sample Input #3

3
2
1 5
2 -1
1 5

Sample Output #3

9

Sample Input #4

6
4
1 -123
2 -123
3 -123
4 -123
4 -123
3 -123

Sample Output #4

0

Sample Input #5

30
4
2 -1358
4 -1405
4 2003
3 -1148
2 -1527
2 -2015
4 -2910
1 2133
2 2185
1 2249
3 1058
1 -1907
2 -3190
1 -2701
3 -2640
1 1685
3 1855
4 2398
3 -3158
2 1947
3 2947
2 -2197
4 1398
2 -3011
4 -1971
1 -2829
1 3094
2 2704
4 -2592
3 2910

Sample Output #5

30566

Notes/Hints

Constraints

• $1 \leq N \leq 150,000$.
• $1 \leq M \leq N$.
• $1 \leq A_i \leq M$ ($1 \leq i \leq N$).
• $-10,000 \leq V_i \leq 10,000$ ($1 \leq i \leq N$).
• All input values are integers.

Subtasks

1. ($ 4 $ points) $ M = 1 $, $N \leq 15$, $V_i \geq 1$ ($1 \leq i \leq N$).
2. ($ 17 $ points) $V_i \geq 1$ ($1 \leq i \leq N$).
3. ($ 21 $ points) $N \leq 15$.
4. ($ 27 $ points) $N \leq 100$.
5. ($ 19 $ points) $M \leq 100$.
6. ($ 12 $ points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test inputs corresponding to that subtask.

The score for each submission is the sum of the points for the subtasks that the submitted source code is considered correct for.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked under the "My Score Status" tab in the "Submission Results".

Sample Explanation 1

Leaving only the $ 2 $-th painting from the left results in a total value of $ V_2 = 123 $. This input example satisfies the constraints of all subtasks.

Sample Explanation 2

Leaving the $ 1 $-th, $ 3 $-th, and $ 4 $-th paintings from the left is optimal. This input example satisfies the constraints of subtasks $ 2, 3, 4, 5, 6 $.

Sample Explanation 3

Leaving all paintings is optimal. This input example satisfies the constraints of subtasks $ 3, 4, 5, 6 $.

Sample Explanation 4

Leaving no paintings is optimal. This input example satisfies the constraints of subtasks $ 3, 4, 5, 6 $.

Sample Explanation 5

This input example satisfies the constraints of subtasks $ 4, 5, 6 $.

见题面 Input 部分

见题面 Output 部分