자선사업가의 선물주기

자선사업가 도석영은 총예산 B단위의 돈으로 N명의 어린이들에게 선물을 주고 싶어합니다.

어린이 i는 선물 가격인 P(i)와 배송비 S(i)가 드는 선물을 요청할 수 있습니다. (따라서 이 선물을 주문하기 위한 총 비용은 P(i)+S(i)가 됩니다.) 

자선사업가 도석영은 자신이 원하는 선물 하나를 평소의 절반 가격에만 주문할 수 있는 특별 쿠폰을 가지고 있습니다.  따라서 자선사업가 도석영이 어린이 i에게 쿠폰을 사용할 경우, 그는 어린이의 선물에 대해 [P(i)/2]+S(i)만을 지불하면 됩니다. (P(i)는 모두 짝수입니다.)

이제, 개발자인 당신은 자선사업가 도석영을 도와 선물을 줄 수 있는 어린이의 최대 수를 계산해주세요.

B의 범위 :  (1 ≤ B ≤ 1,000,000,000) 

N의 범위 :  (1 ≤ N ≤ 1000) 

• 1번째 줄: 두 개의 공백으로 구분된 정수, N과 B.
• 2번째 줄..1+N: i+1번째 줄은 두 개의 공백으로 구분된 정수, P(i)와 S(i)를 포함합니다. (0 ≤ P(i), S(i) ≤ 1,000,000,000)

• 1번째 줄: 자선사업가 도석영이 선물을 줄 수 있는 어린이들의 최대 수.