1148 : Sushi
Problem type : Batch
Time limit : 4.0 second(s)
Memory limit : 16 megabyte(s)

          Benz Blaho ได้ทำการสั่งซูชิชั้นสูงเข้ามารับประทานในร้านอาหารร้านหนึ่งใกล้โรงเรียน

ซูชิชั้นสูงมีลักษณะเป็นแท่งห่อสาหร่ายขนาดยาว n หน่วย ซึ่งยังไม่ได้ตัด (ดูภาพประกอบ) แต่ทางร้านได้ทำ รอยสำหรับตัด มาให้ทั้งสิ้น m รอย คือรอย (R1,R2,…,Rm)
( ที่มา : http://lh3.ggpht.com/_4MUf6T4VzPw/TSyffZBh72I/AAAAAAAASqo/u9OMw2jTRU8/ehou-maki-papercraft-sushi-roll.jpg )

          Benz Blaho มีเพื่อนทั้งสิ้น k คน และต้องการจะแบ่งซูชิที่เขาสั่งมานั้นให้กับเพื่อนๆของเขาทุกคน (ทุกคนจะต้องได้กินซูชิ) เพื่อนแต่ละคนนั้นจะมีค่า ความชอบซูชิ ที่แตกต่างกัน โดยเพื่อนคนที่ i จะมีค่าความชอบซูชิ Pi หากเพื่อนคนที่มีค่าความชอบซูชิ x ได้กินซูชิความยาว y Benz Blaho จะได้รับความสุข x*y หน่วย

          อย่างไรก็ตาม เพื่อนของ Benz Blaho ค่อนข้างจะเรื่องมากเอาการ พวกเขาต้องการให้ Benz Blaho วางแผนการตัดซูชิก่อนทำการตัดจริง โดยการเลือกรอยตัดมา k-1 รอยที่จะใช้ตัด และเมื่อทำการตัดแล้ว เพื่อนคนที่ 1 จะได้กินซูชิชิ้นซ้ายสุด เพื่อนคนที่ 2 จะได้กินซูชิชิ้นถัดไป …. เพื่อนคนที่ k จะได้กินซูชิชิ้นขวาสุด

          จงเขียนโปรแกรมเพื่อหาวิธีการแบ่งซูชิสำหรับ Benz Blaho เพื่อให้เขาได้รับค่าความสุขรวมมากที่สุด

 

          ข้อมูลนำเข้า
บรรทัดแรก
: จำนวนนับ n, m, k  ( 1 < n < 1000000, 1 < k < m < 20000 )
บรรทัดถัดมา : จำนวนนับ m จำนวน คือ R1 R2 … Rm ( 1 < R1 < R2 < … < Rm < n ) แทนระยะของรอยตัดแต่ละรอย วัดจากขอบซ้ายสุดของซูชิ
บรรทัดถัดมา
: จำนวนนับ k จำนวน คือ P1 P2 … Pm ( 1 < Pi < 1000 ) แทนค่าความชอบซูชิของเพื่อนแต่ละคน

          ข้อมูลส่งออก
บรรทัดแรกและบรรทัดเดียวระบุค่าความสุขรวมมากที่สุดที่
Benz Blaho จะได้รับจากการแบ่งซูชิให้เพื่อนทั้ง k คน


โจทย์โดย : สรวิทย์  สุริยกาญจน์ ( PS.int )
นักแสดง :  https://www.facebook.com/benz.blaho
ที่มา : ศูนย์ สอวน. โรงเรียนมหิดลวิทยานุสรณ์


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
10 5 3
1 3 5 8 9 
4 2 2 
36
10 5 3
2 4 6 8 9 
4 3 9 
68

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

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