АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Фермер Жон өөрийн N (1<=N<=1000)  үнээндээ B (1<=B<=1,000,000,000) төгрөгт багтаан бэлэг өгөхийг хүсч байгаа.

i дугаар үнээ P(i) төгрөгийн үнэтэй мөн S(i) хүргэлтийн үнэтэй бэлэг авахыг хүсч байгаа. (Тиймээс фермер Жон бэлгээ захиалахын тулд нийтдээ P(i)+S(i) төгрөгийг төлөх ёстой.) Фермерт сонгосон нэг бэлгээ тал үнээр нь худалдан авах боломжийг олгодог нэг онцгой купон байгаа. Хэрвээ тэр купоноо i дахь үнээний авахыг хүссэн бэлгэнд ашиглавал тэр бэлгэнд P(i)/2+S(i) төгрөг төлөх болж байгаа юм. Хялбар болгох үүднээс бүх бэлгийн үнэ буюу P(i) тэгш тоо өгөгдөнө.

Фермерт, баярлуулж чадах хамгийн олон үнээний тоог хэлж өгч тусална уу.

Input

1-р мөр : Зайгаар тусгаарлагдсан 2 бүхэл тоо болох N ба B.

2...N+1-р мөр : i+1-р мөр i дахь үнээний хүссэн бэлгэний үнэ болон хүргэлтийн үнэ зайгаар тусгаарлагдсан 2 тоо P(i), S(i) өгөгдөнө. (0 <= P(i),S(i) <= 1,000,000,000) P(i) тэгш тоо байна.

Output

1-р мөр : Фермерийн авч чадах бэлгийн тоо.

Example

Input:

5 24

4 2

2 0

8 1

6 3

12 5

Тайлбар : Түүнд 5 үнээ болон 24 төгрөг байгаа. 1-р үнээ 4 төгрөгний үнэтэй 2 төгрөгний хүргэлтийн үнэтэй бэлэг авахыг хүсч байгаа гэх мэт.

Output:

4

Тайлбар : Фермер Жон 3-р бэлгэнд купоноо ашиглан 1-ээс 4-р бэлгүүдийг авч чадна. Үүний нийт үнэ (4+2)+(2+0)+(4+1)+(6+3) = 22. Гэхдээ өөр боломжоор 4 үнээг баярлуулж  болно.