ในการส่งกระแสไฟฟ้าจากต้นทางไปถึงปลายทาง เมื่อไฟฟ้าเดินทางผ่านสายไฟ แรงดันไฟฟ้าจะลดลงไป
เรื่อย ๆ ทำให้ต้องมีการตั้งสถานีเปลี่ยนแรงดันไฟฟ้าเพื่อเพิ่มแรงดันให้อยู่ในเกณฑ์ที่กำหนด แต่การเลือกตำแหน่งที่ตั้งสถานีเปลี่ยนแรงดันไฟฟ้าไม่ใช่เรื่องที่ง่ายนัก เพราะการไฟฟ้าต้องซื้อที่ดินสำหรับตั้งสถานีและราคาที่ดินแต่ละแปลงก็แตกต่างกันไป

กำหนดให้การไฟฟ้าจ่ายกระแสไฟฟ้าโดยเริ่มจากที่ดินแปลงหมายเลข 1 และกระแสไฟถูกส่งผ่านต่อไปยังแปลงหมายเลข 2, 3, 4 ไปเรื่อย ๆ จนถึงปลายทางคือที่ดินแปลงหมายเลข N โดยที่ดินเหล่านี้เรียงต่อกันเป็นเส้นตรงตามลำดับหมายเลขจากน้อยไปมาก ซึ่งในที่นี้หมายเลข 1 คือที่ดินแปลงเริ่มต้น และหมายเลข N คือที่ดินแปลงปลายทาง

นิยามระยะห่างระหว่างสถานีเปลี่ยนแรงดันไฟฟ้าสองแห่งที่อยู่บนที่ดินแปลงหมายเลข a และ b คือ b-a โดยที่ b > a กำหนดเพิ่มเติมว่าสถานีสองแห่งที่ส่งไฟฟ้าถึงกันโดยตรง (คือไม่มีสถานีอื่นมาคั่น) ต้องมีระยะห่างกันไม่เกิน k แปลง นั่นคือ b-a < k และหากการไฟฟ้าต้องการสร้างสถานีในที่ดินแปลงใดก็จะต้องซื้อที่ดินแปลงนั้น สำหรับราคาที่ดินของแปลงหมายเลข 1,2,3,..,n คือ P1,P2,P3,...,Pn ตามลำดับ

          จงเขียนโปรแกรมที่มีประสิทธิภาพในการหาค่าใช้จ่ายรวมที่น้อยที่สุดในการซื้อที่ดินเพื่อตั้งสถานีทั้งหมดสำหรับการส่งกระแสไฟฟ้าจากที่ดินแปลงหมายเลข 1 ไปถึงแปลงหมายเลข n เมื่อกำหนดให้การไฟฟ้าต้องตั้งสถานีในแปลงหมายเลข 1 และหมายเลข n เสมอ

ข้อมูลเข้า

1.       บรรทัดแรกระบุจำนวนแปลงที่ดิน N ที่กระแสไฟจะถูกส่งผ่าน โดยที่ 2 < N < 500 000 

2.       บรรทัดที่สองระบุค่า k แทนระยะห่างซึ่งเป็นจำนวนแปลงที่มากที่สุดระหว่างสถานีสองแห่งที่สามารถส่งไฟฟ้าถึงกันได้โดยตรง โดยที่ 1 < k < N  และ k < 20 000 

3.       บรรทัดที่สาม ประกอบด้วยเลขจำนวนเต็ม N จำนวน คั่นด้วยช่องว่าง เลขเหล่านี้แทนราคาที่ดินของแต่ละแปลงคือ  ตามลำดับ P1,P2,...,Pn โดยที่ 1 < Pi < 2000

ที่มา : การแข่งขันคอมพิวเตอร์โอลิมปิกระดับชาติครั้งที่ 8 (SUTOI8)