EGOI Exhibition

Problem Statement

The JOI Art Museum has N paintings displayed in a single horizontal row. There are M types of paintings in the exhibition, numbered from 1 to M. The type of the i-th painting from the left (1 ≦ i ≦ N) is A_i, and its value is V_i. Note that V_i can be negative.

Next month, the JOI Art Museum is scheduled to hold the "EGOI Exhibition 2022." Since many visitors are expected, the museum wants to improve the visual appeal of the display. Therefore, the director, Rie, decided to remove some paintings so that no two adjacent paintings are of the same type.

On the other hand, to enhance the museum's reputation, she wants to maximize the total value of the remaining paintings.

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

Constraints

• 1 ≦ N ≦ 150000.
• 1 ≦ M ≦ N.
• 1 ≦ A_i ≦ M (1 ≦ i ≦ N).
• - 10000 ≦ V_i ≦ 10000 (1 ≦ i ≦ N).
• All input values are integers.

Input

The input is given from standard input in the following format.
N
M
A₁ V₁
A₂ V₂
:
A_N V_N

Output

Output the maximum possible total value of the remaining paintings in one line to standard output.

Sample Input and Output

Sample Input 1

3
1
1 107
1 123
1 100

Sample Output 1

123

If only the 2nd painting from the left is kept, the total value is V₂ = 123.

Sample Input 2

4
3
1 204
2 168
2 277
1 219

Sample Output 2

700

It is optimal to keep the 1st, 3rd, and 4th paintings from the left.

Sample Input 3

3
2
1 5
2 -1
1 5

Sample Output 3

9

It is optimal to keep all the paintings.

Sample Input 4

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

Sample Output 4

0

It is optimal to keep no paintings at all.

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

---