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

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

          Benz Blaho มีเพื่อนทั้งสิ้น k คน และต้องการจะแบ่งซูชิที่เขาสั่งมานั้นให้กับเพื่อนๆของเขาทุกคน (ทุกคนจะต้องได้กินซูชิ) เพื่อนแต่ละคนนั้นจะมีค่า ความชอบซูชิ ที่แตกต่างกัน โดยเพื่อนคนที่ i จะมีค่าความชอบซูชิ P_i หากเพื่อนคนที่มีค่าความชอบซูชิ 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 จำนวน คือ R₁ R₂ … R_m ( 1 < R₁ < R₂ < … < R_m < n ) แทนระยะของรอยตัดแต่ละรอย วัดจากขอบซ้ายสุดของซูชิ
บรรทัดถัดมา : จำนวนนับ k จำนวน คือ P₁ P₂ … P_m ( 1 < P_i < 1000 ) แทนค่าความชอบซูชิของเพื่อนแต่ละคน

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

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