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 \cdot 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.

Example

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

27

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

0