1056 : Hands
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
มือแมนเป็นยอดมนุษย์ที่เกิดมาเพื่อรับใช้มวลมนุษย์โดยแท้ เขาสามารถทำางานตามสั่งได้ทุกอย่าง และยังเป็นคนที่เกิดมามีมือ K มือจึงสามารถทำางานไปพร้อมๆ กันเป็นชุดๆ ได้มากที่สุดถึง K งาน เพียงแต่ว่าหลังจากมือแมนรับงานชุดใดๆ มาทำแล้ว เขาไม่รับงานใดๆ เข้ามาทำอีกจนกว่างานที่ทำาอยู่จะเสร็จหมดทัง้ ชุด แล้วจึงส่งจากที่ทำาไว้ทัง้ หมดให้คนสั่งพร้อมๆกัน หลังจากนั้น ถึงรับงานชุดถัดไปเข้ามาทำต่อทันที

พิจารณาเมื่อวานมีคนสั่งงานมือแมน 5 คน แต่ละงานใช้เวลา 6, 1, 2, 8, 7 หน่วยตามลำาดับถ้ามือแมนมีวิธีการทำงานดังนี้

ชุดที่ งานต้องใช้เวลา ใช้เวลา จำนวนคนสั่ง เวลาที่รอมาทั้งหมด
1 6 6 1 6
2 1,2 2 2 6+2
3 8,7 8 2 6+2+8


ถ้ากำาหนดให้ เวลาที่คนที่รอมือแมนนานที่สุดเป็นค่า X จะเห็นได้ว่าค่า X มีค่าเป็น 6+2+8 = 16 หน่วย สังเกตว่ามือแมนจัดวิธีการทำางานให้ดีกว่านี้ จะสามารถลดเวลารอของคนที่รอมือแมนนานที่สุดได้

สำาหรับในวันนีเ้หล่ามวลมนุษย์ N คน ขอให้มือแมนทำางานให้เหมือนทุกๆ วัน สำาหรับงานที่ i (เมื่อ 1 <= i <= N) มือแมนจะต้องใช้เวลา Ti หน่วยจึงจะทำงานเสร็จ

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

ข้อมูลป้อนเข้า
บรรทัดแรกระบุจำนวนเต็ม N และ K (1<= N <= 2,000; 1 <= K <= 2,000)
จากนั้น อีก N บรรทัดจะระบุเวลาที่มือแมนต้องใช้สำาหรับงานต่างๆ กล่าวคือสำาหรับ 1 <= i <= N ในบรรทัดที่ i + 1 จะระบุค่า Ti ของ (1 <= Ti <= 1,000)

ข้อมูลส่งออก
มีข้อมูลเพียงบรรทัดเดียว ประกอบด้วยจำานวนเต็มหนึ่ง จำนวนคือค่า X ที่น้อยที่สุดที่เป็นไปได้

ที่มา: Young Thai Online Programming Competition 2008
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 3
6
1
2
8
7		 10

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

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