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

ในเริ่มแรก   แผ่นช็อกโกแลตนี้มีลักษณะเป็นบล็อกเดี่ยวขนาดใหญ่มาก   Bonny ต้องการที่จะหั่นมันให้เป็นบล็อกที่มีขนาดเล็กลงเรื่อย ๆ จนกระทั่งเธอได้หั่นแผ่นช็อกโกแลตนี้เล็กลงจนได้เป็นชิ้นช็อกโกแลตจำนวน N * M ชิ้นในที่สุด   แต่เนื่องจากว่า Bonny กำลังยุ่งมาก ๆ   ดังนั้น เธอจึงต้องการความช่วยเหลือจากผู้ช่วยของเธอที่ชื่อ Sly Peter ในการหั่นแผ่นช็อกโกแลตนี้แทน   สิ่งที่ Peter ต้อง ทำมีเพียงแค่การหั่นเป็นแนวเส้นตรงจากปลายด้านหนึ่งถึงปลายอีกด้านหนึ่งเท่า นั้นและเขาก็ต้องการค่าแรงสำหรับทุก ๆ ครั้งที่เขาได้ลงมือหั่นด้วย   แต่ทว่าตอนนี้ Bonny ไม่มีเงินสดอยู่ในมือ   เธอมีลูกเกดจำนวนมากมายแทน    ดังนั้น เธอจึงเสนอที่จะจ่ายค่าแรงให้แก่ Peter เป็นลูกเกดแทนและ Sly Peter ก็ เห็นด้วยกับข้อตกลงนี้  แต่ทว่าเขาจะต้องได้รับค่าแรงตามเงื่อนไข ดังนี้   ทุกครั้งที่เขาได้ลงมือหั่นบล็อกของช็อกโกแลตที่ได้มา   ออกเป็น 2 บล็อกที่มีขนาดเล็กลง   เขาจะต้องได้รับค่าแรงเป็นลูกเกดจำนวนเท่ากับจำนวนของลูกเกดที่อยู่บน บล็อกช็อกโกแลตที่เขาได้รับมานี้

Bonny ต้องการที่จะจ่ายลูกเกดให้แก่ Peter เป็นจำนวนน้อยที่สุดเท่าที่จะเป็นไปได้   และเธอก็ทราบจำนวนลูกเกดทั้งหมดที่อยู่บนแต่ละชิ้นของช็อกโกแลตจำนวน N * M ชิ้นเหล่านี้   เธอสามารถที่จะเลือกลำดับของการส่งบล็อกช็อกโกแลตที่เหลือให้แก่ Peter ได้และเธอก็ยังสามารถบอก Peter ได้ด้วยว่าเธอต้องการให้เขาหั่นในแนวไหน (แนวนอนหรือแนวตั้ง) และเธอต้องการให้เขาลงมือหั่นที่ตรงตำแหน่งไหนอีกด้วย   เรามาช่วย Bonny ตัดสินใจกันว่า เธอจะสามารถหั่นช็อกโกแลตนี้ออกเป็นชิ้นช็อกโกแลตแต่ละชิ้นได้ยังไง   เพื่อที่เธอจะได้จ่ายค่าแรงให้แก่ Sly Peter เป็นจำนวนลูกเกดที่น้อยที่สุดเท่าที่จะเป็นไปได้

งานของคุณ

จงเขียนโปรแกรมเพื่อรับข้อมูลของจำนวนลูกเกดที่อยู่บนชิ้นช็อกโกแลตแต่ละชิ้น   แล้วพิจารณาหาจำนวนลูกเกดที่น้อยที่สุดที่ Bonny จะต้องจ่ายให้แก่ Sly Peter

เงื่อนไข

1 ≤ N, M ≤ 50       คือ   จำนวนของชิ้นช็อกโกแลตบนแต่ละด้านของแผ่นช็อกโกแลตนี้

1 ≤  R_k,p ≤  1000    คือ   จำนวนของลูกเกดบนชิ้นช็อกโกแลตชิ้นที่อยู่ในตำแหน่งแถวที่ k และคอลัมน์ที่ p

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

โปรแกรมของคุณจะต้องรับข้อมูลเข้ามาทางคีย์บอร์ด   ดังนี้

• ในบรรทัดแรก   ประกอบด้วยเลขจำนวนเต็ม N และ M   แยกกันด้วยช่องว่าง 1 ช่อง
• N บรรทัดถัดมา ให้อธิบายว่ามีจำนวนลูกเกดอยู่บนชิ้นช็อกโกแลตแต่ละชิ้นอยู่จำนวนเท่าไร   โดยในบรรทัดที่ k  ของ N บรรทัดเหล่านี้ให้อธิบายถึงแถวที่ k ของแผ่นช็อกโกแลตนี้   และในแต่ละบรรทัดเหล่านี้จะประกอบด้วยเลขจำนวนเต็ม M ตัว เลขซึ่งแยกกันด้วยช่องว่าง 1 ช่อง   โดยเลขจำนวนเต็มเหล่านี้จะอธิบายถึงชิ้นช็อกโกแลตทั้งหมดซึ่งอยู่ในแถวดัง กล่าวเรียงลำดับจากซ้ายไปขวา   และเลขจำนวนเต็มตัวที่ p บนบรรทัดที่ k  (ของ N บรรทัดเหล่านี้)  จะบอกคุณว่า  มีจำนวนลูกเกดอยู่บนชิ้นช็อกโกแลตชิ้นที่อยู่ในแถวที่ k และคอลัมน์ที่ p อยู่จำนวนเท่าไร

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

โปรแกรม ของคุณจะต้องแสดงผลออกมาทางจอภาพในบรรทัดเดียว   ซึ่งในบรรทัดนี้จะประกอบด้วยเลขจำนวนเต็มค่าเดียวคือ จำนวนลูกเกดที่น้อยที่สุดเท่าที่จะเป็นไปได้ที่ Bonny จะต้องจ่ายให้แก่ Sly Peter

การให้คะแนน

สำหรับการทดสอบ   จะมีค่าทั้งหมด 25 คะแนน เมื่อ N และ M มีค่าไม่เกิน 7

ที่มา: 21^st International Olympiad In Informatics– August 8 - 15, 2009 (Day 1)