1087 : ซื้อบ้าน (house)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)

    บริษัททีโอไอจำกัด เป็นบริษัทที่ทำการขายบ้านในที่ต่าง ๆ และในที่แห่งหนึ่งซึ่งคุณเป็นผู้ดูแลนั้น มีบ้านที่ถูกสร้างวางเป็นช่องตารางจำนวน R×C หลัง บ้านแต่ละหลังจะมีดัชนีค่าความสุขอยู่ค่าหนึ่งเป็นจำนวนเต็มที่ไม่เป็นลบ

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

    ในวันหนึ่ง มีผู้มีพระคุณมาขอซื้อบ้านหนึ่งหลัง และให้คุณเป็นคนเลือกให้ท่าน คุณอยากให้ท่านผู้นั้นได้อาศัยอยู่อย่างมีความสุขมากที่สุด ถามว่าบ้านหลังที่มีค่าความสุขรวมมากที่สุด มีค่าความสุขรวมเท่าไร


งานของคุณ

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

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

    บรรทัดแรกมีจำนวนเต็มบวกสามจำนวน R, C และ K (1≤R,C,K≤300)
    บรรทัดถัดไป R บรรทัดจะมีข้อมูลชองดัชนีความสุขของบ้านในแต่ละหลัง บรรทัดละ C จำนวน โดยจำนวนลำดับที่ j ในบรรทัดที่ i+1 สำหรับ 1≤i≤R  จะมีจำนวน V_ij ซึ่งเป็นค่าความสุขของบ้านแถวที่ i หลักที่ j โดยที่ 0≤V_ij≤10,000


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

      มีบรรทัดเดียว มีจำนวนเต็มหนึ่งจำนวน บอกค่าความสุขรวมที่มากที่สุดที่เป็นไปได้

อธิบายข้อมูลน้ำเข้าและส่งออก

      มีบ้าน 5 แถวๆละ 4 หลัง ระยะทางที่ใช้คำนวณความสุขรวมคือ 2 หลัง และในบ้านในแถวที่ 3 หลักที่ 4 จะทำได้ค่าความสุขรวมเท่ากับ 2 + 5 + 3 + 5 - 0 - 1 - 1 = 13 ดังตัวอย่างด้านล่าง

0    0    0   +5_
0    0    0   -0_
0   +3   -1  [+2]
0    0    0   -1_
0    0    0   +5_

โจทย์โดย: วิสิฐ ภัทรนุธาพร
ที่มา: TOI.C:04-2009

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
5 4 2 2 2 3 5 3 2 4 0 5 3 1 2 0 2 0 1 3 2 1 5	13

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้