MQ là một người hay cáu kỉnh nhưng có rất nhiều bạn. TL là một người bạn thân thiết của MQ và một hôm cậu ấy nghĩ ra \(n\) trò chơi khăm cho bạn mình, mỗi trò chơi khăm có độ vui cho TL và sự tức giận cho MQ. Cụ thể hơn, trò chơi khăm thứ \(i\) sẽ làm TL vui thêm \(a_i\) đơn vị vui và sẽ làm MQ tức giận thêm \(b_i\) đơn vị tức giận.
Tuy nhiên vì trò đùa chỉ vui một lần nên khi TL chơi khăm MQ bằng trò thứ \(i\) thì độ vui của trò đó sẽ bị giảm một nửa (khi làm tròn xuống hàng đơn vị). Cụ thể hơn, khi TL chơi khăm MQ bằng trò thứ \(i\) thì \(a_i=\lfloor \frac{a_i}{2} \rfloor\). Còn \(b_i\) thì giữ nguyên (Vì MQ không biết tĩnh tâm).
Biết MQ chỉ có thể chịu nổi tối đa \(k\) sự tức giận (không thì anh ấy sẽ đốt nhà TL), hãy giúp TL chơi khăm MQ sao cho tổng độ vui của TL là lớn nhất mà không làm MQ đốt nhà mình!

Input

• Dòng đầu tiên gồm 2 số nguyên dương \(n,k\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) gồm 2 số nguyên dương \(a_i, b_i\)
• \(n,k,a_i,b_i\le 1000\)

Output

• Dòng duy nhất gồm tổng độ vui lớn

Example

2 7
8 3
3 5

12