ดูต้นฉบับสำหรับ Gcj2012

== Round 3 ==

=== Problem C. Quality Food ===

Source: [https://code.google.com/codejam/contest/1835486/dashboard#s=p2]

คุณเพิ่งจะย้ายจากเมืองบ้านเกิดไปยังเมืองหลวง! คุณรักทุกอย่างที่เมืองใหญ่เมืองนี้ ยกเว้นเรื่องเดียว คือเรื่องอาหาร  เมืองบ้านเกิดของคุณมีอาหารที่เยี่ยมที่สุดในละแวกนี้ (เราจะเรียกว่า "อาหารคุณภาพ") แน่นอนว่าคุณคิดถึงอาหารชั้นยอดนั้นมาก

โชคดีที่ร้านอาหารใหญ่ที่สุดที่เมืองบ้านเกิดของคุณมีบริการส่งอาหาร  คุณสามารถซื้ออาหารปริมาณเท่าใดก็ได้ต่อการส่งหนึ่งครั้ง  ในการส่งหนึ่งครั้งจะมีค่าจัดส่งเป็นค่าคงที่ ซึ่งไม่ขึ้นกับปริมาณอาหารที่คุณสั่ง

ร้านอาหารร้านนี้มีอาหารหลายแบบ อาหารแต่ละประเภทจะมีคุณสมบัติสองอย่าง คือ ราคาต่อมื้อ และ เวลาที่จะเสีย  อาหารมื้อหนึ่งจะสามารถทำให้คุณมีชีวิตอยู่ได้อีกหนึ่งวัน  เมื่ออาหารมื้อนั้นถูกรับประทานแล้ว ก็จะไม่สามารถนำมารับประทานซ้ำได้  เวลาที่จะเสียของอาหารคือจำนวนวันที่มากที่สุดที่อาหารนั้นยังสามารถใช้รับประทานได้อยู่ เริ่มนับจากวันที่คุณได้รับอาหารนั้น อาหารที่มีเวลาที่จะเสียเท่ากับศูนย์หมายความว่าเป็นอาหารที่คุณต้องรับประทานในวันที่ได้รับอาหารนั้นเลย

ในการส่งอาหารครั้งหนึ่ง คุณสามารถซื้ออาหารกี่แบบก็ได้ แบบละกี่มื้อก็ได้ ตราบเท่าที่คุณมีเงินพอจ่าย  สังเกตว่าถ้าอาหารประเภทหนึ่งมีเวลาเสียเท่ากับ t  มันจะไม่มีประโยชน์อะไรที่จะซื้ออาหารนั้นมามากกว่า t+1 มื้อต่อการส่งหนึ่งครั้ง เพราะว่าจะมีบางมื้อเสียก่อนที่คุณจะได้รับประทานมัน

ร้านอาหารนี้มีการจัดการส่งอาหารอย่างดีเยี่ยม  คุณจะได้รับอาหารที่สั่งในวันเดียวกับที่คุณซื้อ และคุณสามารถรับประทานอาหารที่สั่งได้ในวันนั้นเลย   การซื้ออาหารโดยการสั่งนี้ เป็นวิธีเดียวที่คุณจะมีอาหารคุณภาพรับประทาน

ให้จำนวนเงินที่คุณสามารถใช้ซื้ออาหารและจ่ายค่าส่ง ให้คำนวณหาจำนวนวันที่มากที่สุดที่คุณสามารถรับประทานอาหารคุณภาพได้ทุกวัน