Paul เป็นเจ้าของบริษัทจัดเลี้ยงและธุรกิจกำลังรุ่งเรือง บริษัทมีทีมจัดเลี้ยง $k$ ทีม แต่ละทีมรับผิดชอบอุปกรณ์จัดเลี้ยงหนึ่งชุด ทุกสัปดาห์บริษัทรับคำขอจัดเลี้ยงสำหรับงานต่าง ๆ $n$ รายการ สำหรับแต่ละคำขอ บริษัทจะส่งทีมพร้อมอุปกรณ์ไปยังสถานที่จัดงาน ทีมจะส่งอาหาร ติดตั้งอุปกรณ์ และสอนเจ้าภาพให้ใช้อุปกรณ์และเสิร์ฟอาหาร หลังงานจบ เจ้าภาพมีหน้าที่นำอุปกรณ์กลับมาคืนบริษัทของ Paul

ภาพจาก Wikimedia Commons

แต่น่าเสียดายที่บางสัปดาห์จำนวนทีมจัดเลี้ยงน้อยกว่าจำนวนคำขอ จึงอาจต้องใช้บางทีมให้บริการมากกว่าหนึ่งงาน ในกรณีนี้บริษัทไม่สามารถรอให้เจ้าภาพคืนอุปกรณ์ แต่ต้องให้ทีมอยู่ที่สถานที่จัดงานเพื่อขนย้ายอุปกรณ์ไปยังสถานที่อื่น บริษัทมีค่าประมาณที่แม่นยำของค่าใช้จ่ายในการย้ายอุปกรณ์หนึ่งชุดจากสถานที่ใด ๆ ไปยังสถานที่อื่นใด ๆ เมื่อกำหนดค่าใช้จ่ายเหล่านี้ Paul ต้องการจัดทำ Advance Catering Map เพื่อให้บริการตามคำขอโดยลดค่าใช้จ่ายรวมในการย้ายอุปกรณ์ให้ต่ำที่สุด (รวมการย้ายครั้งแรกด้วย) แม้นั่นจะหมายถึงการไม่ได้ใช้ทุกทีมที่มีอยู่ Paul ต้องการให้คุณช่วยเขียนโปรแกรมทำงานนี้ คำขอเรียงตามเวลาของงานจากน้อยไปมาก และถูกเลือกมาให้สำหรับทุก $i<j$ มีเวลาเพียงพอที่จะขนอุปกรณ์ที่ใช้ในคำขอที่ $i$ ไปยังสถานที่ของคำขอที่ $j$

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มสองจำนวน $n$ ($1 \le n \le 100$) และ $k$ ($1 \le k \le 100$) ซึ่งเป็นจำนวนคำขอและจำนวนทีมจัดเลี้ยงตามลำดับ จากนั้นมี $n$ บรรทัด โดยบรรทัดที่ $i$ มีจำนวนเต็ม $n-i+1$ จำนวน ซึ่งอยู่ระหว่าง $0$ ถึง $1\,000\,000$ รวมขอบเขตทั้งสอง จำนวนที่ $j$ ในบรรทัดที่ $i$ คือค่าใช้จ่ายในการย้ายอุปกรณ์หนึ่งชุดจากสถานที่ $i$ ไปยังสถานที่ $i+j$ บริษัทอยู่ที่สถานที่ $1$ และคำขอทั้ง $n$ รายการอยู่ที่สถานที่ $2$ ถึง $n+1$

ข้อมูลส่งออก

แสดงค่าใช้จ่ายในการย้ายที่ต่ำที่สุดเพื่อให้บริการครบทุกคำขอ (จำนวนนี้ไม่รวมค่าใช้จ่ายในการนำอุปกรณ์กลับบริษัทจัดเลี้ยง)

ตัวอย่าง

ข้อมูลนำเข้า 1

3 2
40 30 40
50 10
50

ข้อมูลส่งออก 1

80

ข้อมูลนำเข้า 2

3 2
10 10 10
20 21
21

ข้อมูลส่งออก 2

40