Bạn có \(n\) hóa đơn, với mỗi hóa đơn gồm tên khách hàng và số tiền khách hàng phải trả, có thể có nhiều hóa đơn là của một người.

Bây giờ bạn cần chọn ra \(k\) người trong đống hóa đơn đó sao cho tổng số tiền của \(k\) người đó là lớn nhất. Nếu \(k\) lớn hơn số người trong đống hóa đơn đó thì bạn có thể chọn hết.

Gọi \(c\) là độ dài tối đa cho tên của một khách hàng.

Input

• Dòng đầu tiên gồm 2 số nguyên \(n\) và \(k\).
• \(n\) dòng tiếp theo gồm chuỗi \(S_i\) là tên khách hàng (không có dấu cách) và số nguyên \(a_i\) là số tiền của hóa đơn thứ \(i\).
• Ràng buộc:
  • \(1 \le a_i \le 10^9\)

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Example

6 1
uvuvwevwevweonyetenyevweugwemubwemossas 10
ryuk 11
uvuvwevwevweonyetenyevweugwemubwemossas 5
fegla 3
tenshikanade 7
fegla 2

15

7 2
waynebot 7
lhic 4
petr 5
umnik 9
izrak 6
tourist 11
zlobobber 9

20

Scoring

• Subtask \(1\) (\(40\%\) số điểm):
  • \(1 \leq n \leq 100\)
  • \(1 \leq c \leq 2\)
• Subtask \(2\) (\(30\%\) số điểm):
  • \(1 \leq n \leq 10^5\)
  • \(1 \leq c \leq 30\)
• Subtask \(3\) (\(30\%\) số điểm):
  • \(1 \leq n \leq 2 \cdot 10^5\)
  • \(1 \leq c \leq 100\)