# JOIGSC Exhibition

www.acmicpc.net/problem/24424

At the JOI Art Museum, there are $N$ paintings displayed in a row. There are $M$ different types of paintings, and each type is labeled with an integer from $1$ to $M$.

The $i$-th painting from the left:
- Is of type $A_i$,
- Has a value of $V_i$, which may be negative.

Next month, the EGOI Exhibition 2022 is scheduled to be held at the JOI Art Museum. Since many visitors are expected, the museum director, Rie, wants the display to look better. To improve the aesthetics, she plans to remove some paintings so that no two adjacent paintings are of the same type.

At the same time, to boost the exhibition’s reputation, she wants to maximize the total value of the remaining paintings.

Given the number of paintings, the number of types, and the list of paintings, your task is to determine the maximum possible total value of the paintings that can remain, under the constraint that no two adjacent paintings are of the same type.

## Input

Input is given from standard input in the following format:

> N
> M
> A_1 V_1
> A_2 V_2
> :
> A_N V_N

## Output

Output a single integer on a single line: the maximum total value of the remaining paintings.
Constraints

* $1 \leq N \leq 150,000$
* $1 \leq M \leq N$
* $1 \leq A_i \leq M$ for all $1 \leq i \leq N$
* $-10,000 \leq V_i \leq 10,000$ for all $1 \leq i \leq N$
* All input values are integers

## Subtasks

## Samples

### Example Input 1

3
1
1 107
1 123
1 100

### Example Output 1

`123`

Explanation: Keeping only the second painting results in the highest value of $123$.

### Example Input 2

4
3
1 204
2 168
2 277
1 219

### Example Output 2

700

Explanation: Keeping the 1st, 3rd, and 4th paintings (types 1, 2, 1) yields a total value of $204 + 277 + 219 = 700$.

### Example Input 3

3
2
1 5
2 -1
1 5

### Example Output 3

`9`

All paintings can remain, as no adjacent paintings are of the same type, and the total value is $5 + (-1) + 5 = 9$.

### Example Input 4

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

### Example Output 4

0

Removing all paintings is optimal here, since all values are negative.

### Example 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

### Example Output 5

30566