Usaco2013

USACO 2013 February Contest, Gold

Problem 1: Partitioning the Farm [Brian Dean, 2013]

Source: [1]

ฟาร์มของชาวนาจอห์นแบ่งเป็นช่องตารางกริดขนาด N x N (2 <= N <= 15) ตอนนี้ที่ฟาร์มมีแค่รั้วล้อมภายนอกฟาร์ม แต่วัวสามารถเดินไปมาระหว่างช่องในฟาร์มได้

ชาวนาจอห์นตัดสินใจว่าจะสร้างรั้วเพื่อแบ่งวัวออกเป็นกลุ่ม ๆ เนื่องจากกฎหมายการแบ่งโซน รั้วที่สร้างจะต้องเป็นรั้วในแนวตั้งหรือแนวนอน และมีความยาวจากขอบฟาร์มด้านหนึ่งไปยังขอบอีกด้านหนึ่ง และรั้วจะไม่สามารถสร้างผ่านช่องของตารางกริด ชาวนาจอห์นมีเงินมากพอที่จะสร้างรั้วได้แค่ K รั้วเท่านั้น (1 <= K <= 2N-2)

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

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

• บรรทัด 1: จำนวนเต็มสองจำนวน N และ K
• บรรทัด 2..1+N: แต่ละบรรทัดมีจำนวนเต็ม N จำนวน แทนจำนวนวัวในแต่ละช่องในแถวหนึ่ง ๆ ของฟาร์ม (จำนวนวัวจะมีค่าไม่น้อยกว่า 0 และไม่เกิน 1 000 ตัว ในแต่ละช่อง

ตัวอย่าง input

3 2
1 1 2
1 1 2
2 2 4

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

มีบรรทัดเดียว เป็นขนาดของกลุ่มวัวที่ใหญ่ที่สุด ที่น้อยที่สุดที่เป็นไปได้

ตัวอย่าง

4

คำอธิบาย

ชาวนาจอห์นควรจะสร้างรั้วระหว่างคอลัมน์ 2 และ 3, และระหว่างแถวที่ 2 และ 3 ซึ่งจะทำให้มีกลุ่มวัว 4 กลุ่ม กลุ่มละ 4 ตัว