Lisa là bạn tin vào may mắn. Khi bạn ý làm contest thứ i trên HCNOJ bạn ý luôn có 2 giá trị L[i] và T[i] trong đó L[i] là chỉ số may mắn khi làm contest đó và T[i] là chỉ số quan trọng của contest (bằng 1 nếu contest thứ i là quan trọng và bằng 0 nếu contest thứ i là không quan trọng)

Nếu Lisa làm đúng contest thứ i thì chỉ số may mắn của bạn ý sẽ bị giảm đi 1 lượng L[i], nếu làm sai sẽ được cộng 1 lượng L[i]

Nếu Lisa làm sai không nhiều hơn k contest quan trọng thì chỉ số may mắn tối đa mà Lisa có sẽ là bao nhiêu?

Ràng buộc:

1 <= n <= 100

0 <= k <= n

1 <= Li <= 10^4

0 <= Ti <= 1

Đầu vào: Dòng đầu tiên gồm 2 số, số thứ nhất mô tả số lượng contest, số thứ 2 là k

Các dòng tiếp theo lần lượt là giá trị L[i] và T[i] của từng contest

Input:

6 3
5 1
2 1
1 1
8 1
10 0
5 0

Output:

29