หอดูดาว (toi11_observatory)


Time limit:
1000 ms
Memory limit:
512 MB

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

หัวหน้าช่างได้ออกแบบหอดูดาวที่มีฐานเป็นรูปสามเหลี่ยมมุมฉาก ซึ่งมีด้านประกอบมุมฉากมีขนาดเท่ากันยาวด้านละ K หน่วย รายาบุหรงมีความพอพระทัยในแบบของหอดูดาวเป็นอันมาก จึงได้ดำริมอบหมายให้มุขมนตรีหาที่ตั้งในการสร้างหอดูดาวที่มีฐานเป็นรูปร่างดังกล่าว ในบริเวณที่ว่างบนเนินเขาที่มีขนาดพื้นที่ M x N ตารางหน่วย ทางมุขมนตรีจึงมอบหมายให้หัวหน้าช่างไปศึกษาข้อมูลความสูงของที่ว่างบนเนินเขาแห่งนี้ ผลปรากฏว่าแต่ละตารางหน่วยของที่ว่างมีความสูงแตกต่างกันออกไป โดยหัวหน้าช่างได้บันทึกความสูงของพื้นที่แต่ละตารางหน่วยเป็นจํานวนเต็มบวกในกรณีที่ตารางหน่วยนั้นสูงกว่าระดับน้ำทะเล และเป็นจํานวนเต็มลบในกรณีที่ตารางหน่วยนั้นต่ำกว่าระดับน้ำทะเล ส่วนกรณีที่ความสูงเท่ากับระดับน้ำทะเลพอดีจะถูกบันทึกเป็นจํานวนเต็มศูนย์

เพื่อให้หอดูดาวเป็นไปตามแบบที่ต้องการ จึงมีการกําหนดเงื่อนไขสำคัญสองข้อ คือ

1. ด้านประกอบมุมฉากของสามเหลี่ยมทั้งสองด้านซึ่งยาว K หน่วย และด้านทั้งสองจะต้องขนานกับด้าน M และ N ของพื้นที่ว่าง ในลักษณะตามรูปแบบสองรูปแบบต่อไปนี้ อย่างใดอย่างหนึ่งเท่านั้น

2. หอดูดาวนี้ต้องตั้งอยู่บนพื้นที่ที่มีความสูงรวมมากที่สุด (ผลรวมของความสูงจากระดับน้ำทะเลของทุกตารางหน่วยที่ใช้มีค่ามากที่สุด) โดยความสูงของตารางหน่วยที่ใช้ไม่มีการตัดแบ่ง

ตัวอย่างที่ 1 พื้นที่ที่ถูกเลือกเพื่อสร้างหอดูดาวที่มี K = 3 อยู่ในบริเวณที่แรเงา

จากตัวอย่างที่ 1 ที่ว่างบนเนินเขาขนาด 4 x 5 ตารางหน่วย แต่ละตารางหน่วยมีความสูงเทียบกับระดับน้ำทะเลตามตัวเลขที่ระบุไว้ในแต่ละตารางหน่วย พื้นที่ที่ถูกเลือกตามข้อกําหนดเพื่อสร้างหอดูดาวที่มีฐานรูปสามเหลี่ยมซึ่งมีความยาวด้านประกอบมุมฉากยาว 3 หน่วย คือตารางหน่วยที่ถูกแรเงาดังรูป ในตัวอย่างนี้ความสูงรวมมากที่สุดของพื้นที่หอดูดาวเท่ากับ 22 หน่วยจากระดับน้ำทะเล

ตัวอย่างที่ 2 พื้นที่ที่ถูกเลือกเพื่อสร้างหอดูดาวที่มี K = 4 อยู่ในบริเวณที่แรเงา (เป็นไปได้ 2 รูปแบบ)

จากตัวอย่างที่ 2 ที่ว่างบนเนินเขาขนาด 6 x 7 ตารางหน่วย แต่ละตารางหน่วยมีความสูงเทียบกับระดับน้ำทะเลตามตัวเลขที่ระบุไว้ในแต่ตารางหน่วย พื้นที่ที่ถูกเลือกตามข้อกําหนดเพื่อสร้างหอดูดาวที่มีฐานรูปสามเหลี่ยมซึ่งมีความยาวด้านประกอบมุมฉากยาว 4 หน่วย คือตารางหน่วยที่ถูกแรเงาดังรูป ซึ่งในตัวอย่างนี้มีพื้นที่สองพื้นที่ที่มีความสูงรวมมากที่สุดเท่ากัน คือ -47 หน่วยจากระดับน้ำทะเล

จงเขียนโปรแกรมคอมพิวเตอร์ที่มีประสิทธิภาพเพื่อคํานวณหาค่าความสูงรวมมากที่สุดของพื้นที่หอดูดาวตามพระประสงค์ของรายาบุหรง

Input

บรรทัดแรก มีจํานวนเต็มสามจํานวน M, N และ K แต่ละจํานวนถูกคั่นด้วยช่องว่างหนึ่งช่องว่าง โดยที่ M แสดงความกว้าง, N แสดงความยาวของที่ว่างบนเนินเขา และ K แสดงความยาวของด้านประกอบมุมฉากของฐานของหอดูดาว กําหนดให้ 2 ≤ M, N ≤ 2,000 และ 1 ≤ K ≤ 1,000 โดยที่ K < M และ K < N

บรรทัดที่ 2 ถึง M + 1 แต่ละบรรทัดประกอบด้วยจํานวนเต็ม N จํานวน แต่ละจํานวนแสดงค่า hi ซึ่งแสดงระดับความสูงจากระดับน้ำทะเลของที่ดินในตารางหน่วยที่ i ของแถวและแต่ละจํานวนถูกคั่นด้วยช่องว่างหนึ่งช่อง กําหนดให้ -500 ≤ hi ≤ 500 และ 1 ≤ i ≤ N

Output

มีหนึ่งบรรทัด ระบุค่าความสูงรวมมากที่สุดของพื้นที่ของหอดูดาว ตามพระประสงค่ของรายาบุหรง

Constrains/Subtasks

อย่างน้อย 10% ของข้อมูลทดสอบ M ≤ 20, N ≤ 20

อย่างน้อย 40% ของข้อมูลทดสอบ M ≤ 600, N ≤ 2000

Editor:

Source: Thailand Olympiad in Informatics 2015 (TOI11 / TOI 2015)

Select description language

Thai (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None