1108 : สายแร่แห่งพลัง 2 (ore2)
Problem type : Batch
Time limit : 0.5 second(s)
Memory limit : 64 megabyte(s)

         เมืองเฟอรอนเป็นเมืองลอยฟ้า มันต้องใช้พลังงานสูงในการขับเคลื่อนตัวเองให้ลอยอยู่เหนือพื้นดิน แต่พลังงานที่ได้จากโรงไฟฟ้านิวเคลียร์กว่าร้อยแห่งบนเมืองนี้มันยังมีไม่ มากพอ เนื่องจากท่านคิงส์เฟอร์เคยเรียนอยู่ในโรงเรียนนักวิจัยที่มีชื่อเสียงแห่ง หนึ่ง ทำให้เขามีความสามารถในการวิเคราะห์และสกัดพลังงานออกมาจากแร่ชนิดต่างๆได้ เขาค้นพบแร่ที่ทรงพลังชนิดหนึ่ง มันมีชื่อว่า “เฟอเร่” แร่ชนิดนี้จะอยู่เรียงชิดติดกันเป็นเส้นตรงความยาว N ชิ้น โดยแต่ละชิ้นสามารถสกัดเป็นพลังงานออกมาได้ Ei เฟอรูล (คล้ายกับหน่วยจูลในระบบเอสไอ) ในการสกัดพลังงานจากแร่ชนิดนี้ เราไม่สามารถสกัดมันทีละชิ้นๆได้ เราจำเป็นต้องสกัดทุกๆชิ้นที่อยู่ติดกันพร้อมกันในคราวเดียว (ได้พลังงานเท่ากับผลรวมของพลังงานที่จะได้จากการสกัดแร่แต่ละชิ้น) แต่ทว่าหากเราสกัดแร่ที่มีพลังงานรวมกันมากกว่า K เฟอ รูลออกมาในครั้งเดียว ด้วยความทรงพลังของแร่เฟอเร่ มันอาจจะก่อให้เกิดการระเบิดที่น่าสะพรึงกลัวกว่าระเบิดนิวเคลียร์ก็เป็นได้ คิงส์เฟอร์จึงต้องทำลายแร่บางชิ้นทิ้งไปเพื่อให้สายแร่ความยาว N นี้แยกออกเป็นสายแร่สั้นๆหลายๆสาย โดยแต่ละสายจะต้องมีผลรวมของพลังงานที่จะสกัดได้ไม่เกิน K เฟอรูล (แร่ที่เลือกทำลายทิ้งเพื่อแบ่งสายแร่ออกเป็นสายย่อยๆ จะไม่สามารถนำมาสกัดเป็นพลังงานได้)

 

          เนื่องจากสายแร่เฟอเร่นั้นเป็นสายแร่หายาก เมื่อคิงส์เฟอร์หามันมาได้สายหนึ่ง เขาจึงต้องการที่จะใช้ประโยชน์จากมันให้ได้มากที่สุด 

          อย่างไรก็ตาม ในตอนแรกนั้นความยาวสายแร่มีได้อย่างมาก 2000 แต่นั่นทำให้คิงพีเอสอิ๊นไม่พอใจเพราะโจทย์มันจะง่ายไป เขาจึงเพิ่มความยาวของสายแร่เป็น 1000000

ข้อมูลนำเข้า

 

          บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน N และ K คั่นด้วยช่องว่าง 1 ช่อง (1 < N < 1000 000, 1 < K < 1 000 000 000) แทนจำนวนแร่เฟอเร่ในสายแร่ที่คิงส์เฟอร์หามาได้ และพลังงานสูงสุดที่ไม่ทำให้เกิดการระเบิด ในบรรทัดถัดไปประกอบด้วยจำนวนเต็ม N ตัว แต่ละตัวถูกคั่นด้วยช่องว่าง 1 ช่อง แสดงค่า Ei สำหรับ 1 < i < N (1 < Ei < 1 000 000) แทนพลังงานที่ได้จากการสกัดแร่ชิ้นที่ i บนสายแร่ ในหน่วยเฟอรูล

ข้อมูลส่งออก

           มีบรรทัดเดียวโดยให้แสดงค่าพลังงานสูงสุดที่คิงส์เฟอร์จะได้จากการสกัดสายแร่เฟอเร่สายนี้ โดยไม่ก่อให้เกิดการระเบิด (ตอบในหน่วยเฟอรูล)

หมายเหตุ

          25% ของชุดทดสอบทั้งหมด n < 10
            50% ของชุดทดสอบทั้งหมด n < 1000
            100% ของชุดทดสอบทั้งหมด n < 1000 000

โจทย์โดย : จิรายุ ชิว ชิว

ที่มา : FOI ( Fur Olympiad in Informatics ) และ ศูนย์ สอวน. โรงเรียนมหิดลวิทยานุสรณ์


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 1
1 2 3 4 5
 1
5 3
1 2 3 1 2
 6
6 1000
1 2 3 4 5 6
 21

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 13 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)