Gcj2012

Round 3

Problem C. Quality Food

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

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

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

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

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

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