Có ~n~ đồ vật. Mỗi đồ vật này thuộc một trong ba loại: chai có nắp bật, chai cần dụng cụ mở và dụng cụ mở chai. Đồ vật thứ ~i~ được mô tả bằng một cặp số nguyên ~(t_i, x_i)~ như sau:

• Nếu ~t_i = 0~, đồ vật thứ ~i~ là một chai có nắp bật. Nếu lấy nó, bạn sẽ nhận được niềm vui là ~x_i~;

• Nếu ~t_i = 1~, đồ vật thứ ~i~ là một chai cần dụng cụ mở. Nếu lấy nó và dùng dụng cụ mở chai để mở nó, bạn sẽ nhận được niềm vui là ~x_i~;

• Nếu ~t_i = 2~, đồ vật thứ ~i~ là một dụng cụ mở chai. Nó có thể được sử dụng để mở tối đa ~x_i~ chai.

Hãy tìm tổng số niềm vui tối đa mà bạn có thể nhận được bằng cách chọn ~m~ trong số ~n~ đồ vật.

Input

Dòng đầu tiên chứa số nguyên ~n~ và ~m~ ~(1 \le m \le n \le 2 \times 10^5)~.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa hai số nguyên ~t_i~ và ~x_i~ ~(0 \le t_i \le 2; 1 \le x_i \le 10^9)~.

Output

In ra một số nguyên là câu trả lời.

Scoring

Sample Input 1

8 4
0 6
0 6
1 3
1 5
1 15
2 1
2 10
2 100

Sample Output 1

27

Sample Input 2

5 5
1 5
1 5
1 5
1 5
1 5

Sample Output 2

0

Notes

Trong ví dụ đầu tiên: Nếu bạn có được đồ vật thứ ~1, 2, 5, 7~ và sử dụng đồ vật thứ ~7~ (một dụng cụ mở chai) để mở đồ vật thứ ~5~, bạn sẽ nhận được tổng niềm vui là ~6 + 6 + 15 = 27~. Không có cách nào để chọn được ~4~ đồ vật có tổng niềm vui lớn hơn ~27~, nhưng bạn vẫn có thể có được tổng niềm vui là ~27~ nếu chọn đồ vật thứ ~6~ hoặc ~8~ thay cho đồ vật thứ ~7~ trong cách chọn trên.