กุลีแห่งท่าเรือ (toi11_labor)


Time limit:
1000 ms
Memory limit:
32 MB

รัชสมัยของรายาบุหรงเป็นยุคทองของการค้าขายทางทะเลของบุหงาตันหยงนคร เหล่าพ่อค้าต่างถือท่าเรือของบุหงาตันหยงนครเป็นจุดหมายสําคัญ ในการเทียบเรือสําเภาเพื่อขนถ่ายแลกเปลี่ยนสินค้า

นายท่าแห่งบุหงาตันหยงนครได้ว่าจ้างกุลีที่แข็งแรงทั้งหมด M คน เพื่อเตรียมไว้ให้บริการเรือสำเภาที่มาเทียบท่า กุลีแต่ละคนมีความแข็งแรงแตกต่างกันออกไป จึงทําให้เวลาที่ใช้ในการขนสินค้าของกุลีแต่ละคนแตกต่างกันไป สําหรับกุลีคนที่ i (1 ≤ i ≤ M) จะใช้เวลา ti นาที นับตั้งแต่เริ่มขนถ่ายสินค้าชิ้นหนึ่งจนกระทั่งขนเสร็จและพร้อมที่จะขนถ่ายสินค้าชิ้นต่อไป

เรือสำเภาจะมีสินค้าขนาดเท่าๆ กันทั้งสิ้น N ชิ้น และมีความเป็นไปได้ที่นายท่าจะมอบหมายหน้าที่ขนถ่ายสินค้าของเรือสําเภานั้นให้กุลีเพียงบางคน โดยกุลีที่ได้รับมอบหมายจะสามารถขนถ่ายสินค้าทั้ง N ชิ้นของเรือสําเภาได้ภายในเวลาน้อยที่สุดเท่าที่เป็นไปได้ เมื่อเรือสําเภาเทียบท่า กุลีที่ได้รับมอบหมายจะเริ่มขนถ่ายสินค้าพร้อมกันทันที และจะขนสินค้าต่อเนื่องอย่างไม่หยุดพักแม้แต่เสี้ยววินาที

ตัวอย่างที่ 1 การขนถ่ายสินค้าของเรือสําเภาที่มีสินค้าห้าชิ้น (N = 5) ซึ่งใช้เวลารวมน้อยที่สุด
โดยมอบหมายงานให้กุลีทั้งหมดที่มีอยู่ จํานวนสองคน (M = 2)

จากตัวอย่างที่ 1 ในการขนถ่ายสินค้าแต่ละชิ้น กุลีคนที่หนึ่งใช้เวลา 7 นาที และคนที่สองใช้เวลา 12 นาที ดังนั้นเวลารวมในการขนถ่ายสินค้าของเรือสําเภาทั้งห้าชิ้นโดยกุลีทั้งสองคนคือ 24 นาที และเป็นเวลารวมที่น้อยที่สุดด้วย

ตัวอย่างที่ 2 วิธีหนึ่งของการขนถ่ายสินค้าของเรือสําเภาที่มีสินค้าสามชิ้น (N = 3)  
ซึ่งใช้เวลารวมน้อยที่สุด โดยมอบหมายงานให้กุลีสองคนจากที่มีอยู่ทั้งหมดสามคน (M = 3)

จากตัวอย่างที่ 2 ในการขนถ่ายสินค้าแต่ละชิ้น กุลีคนที่หนึ่งใช้เวลา 6 นาที คนที่สองใช้เวลา 13 นาที และคนที่สามใช้เวลา 2 นาที ดังนั้นเวลารวมที่น้อยที่สุดในการขนถ่ายสินค้าของเรือสําเภาทั้งสามชิ้น คือ 6 นาที ทําได้สองวิธี คือมอบหมายงานให้กุลีคนที่หนึ่งและคนที่สาม หรือมอบหมายงานให้กุลีคนที่สามเพียงคนเดียว

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

Input

บรรทัดแรก มีจํานวนเต็มสองจํานวน ประกอบด้วย M ระบุจํานวนกุลี และ N ระบุจํานวนสินค้าของเรือสําเภา โดยแต่ละจํานวนถูกคั่นด้วยช่องว่างหนึ่งช่องว่าง กําหนดให้ 2 ≤ M ≤ 1,000,000 และ 1 ≤ N ≤ 1012

บรรทัดที่ 2 ถึง M + 1 แต่ละบรรทัดประกอบด้วย จํานวนเต็มหนึ่งจํานวน คือ ti ซึ่งระบุเวลาที่กุลีคนที่ i ใช้ในการขนถ่ายสินค้าแต่ละชิ้น กําหนดให้ 1 ≤ ti ≤ 1,000,000 และ 1 ≤ i ≤ M

Output

มีหนึ่งบรรทัด ระบุเวลารวมน้อยที่สุด ซึ่งกุลีที่ได้รับมอบหมายสามารถขนถ่ายสินค้าทั้งหมดของเรือสําเภาจนเสร็จ

Constrains/Subtasks

  • อย่างน้อย 10% ของข้อมูลทดสอบ N ≤ 100, M ≤ 1,000, ti ≤ 1,000
  • อย่างน้อย 20% ของข้อมูลทดสอบ N ≤ 10,000, M ≤ 1,000, ti ≤ 100
  • อย่างน้อย 40% ของข้อมูลทดสอบ N ≤ 200,000, M ≤ 5,000, ti ≤ 1,000,000
  • อย่างน้อย 50% ของข้อมูลทดสอบ N ≤ 500,000, M ≤ 100,000, ti ≤ 1,000,000

Editor:

Source: Thailand Olympiad in Informatics 2015 (TOI11 / TOI 2015)

Select description language

Thai (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None