농부 존은 새 소들이 필요하다! 현재 N(1 \le N \le 50,000)마리의 소가 판매 중이고 농부 존은 최대 M(1 \le M \le 10^{14})원을 사용할 수 있다.

i번째 소를 구입하려면 P_i(1 \le P_i \le 10^9)의 비용이 들지만, 농부 존에게는 K(1 \le K \le N)개의 쿠폰이 있다.

어떠한 소를 구입 할 때 쿠폰을 사용하면 소의 가격은 P_i원 대신 C_i(1 \le C_i \le P_i)원이 된다.

하지만 당연하게도 농부 존은 소 한마리당 한장의 쿠폰을 사용할수있다.

농부 존이 최대로 살 수 있는 소의 마릿수를 출력하라.

쿠폰 timer 1s memory 128MB

쿠폰 1s 128MB