0037 : บินดูไฟ (skylight)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
ในวันปีใหม่ สนามกีฬาแห่งหนึ่งได้ประดับไฟที่พื้นสนามฟุตบอลเพื่อความสวยงาม ในการประดับไฟนั้นทำโดยแบ่งสนามสี่เหลี่ยมเป็นช่องย่อยๆ จำนวน N แถว แถวละ M คอลัมน์ รวม N×M ช่อง เจ้าของสนามได้เปิดสนามให้ประชาชนทั่วไปเข้าชมเพื่อความสวยงาม

อย่างไรก็ตาม โลกนี้ไม่มีอะไรฟรี เจ้าของสนามจะต้องจ่ายค่าไฟให้กับไฟประดับเหล่านี้ เนื่องจากมีการประดับไฟเป็นลวดลายต่างๆ ค่าไฟของไฟแต่ละช่องไม่จำเป็นต้องเท่ากัน

เพื่อไม่ให้เป็นการขาดทุน เจ้าของสนามจึงได้จัดเครื่องไอพ่นเจ็ตส่วนบุคคลให้กับประชาชนเช่าเพื่อบินดูไฟประดับ เครื่องพ่นเจ็ตแต่ละเครื่องเมื่อเช่าไปแล้วจะผู้ใช้จะสามารถบินได้ทั้งสิ้น K ครั้ง ในการบินแต่ละครั้งจะใช้เชื้อเพลิงมูลค่าเท่ากับ L บาท 
ดังนั้น ค่าใช้จ่ายรวมทั้งหมดของเจ้าของสนามคือค่าไฟรวมของไฟประดับ และค่าเชื้อเพลิงรวมของการบินเครื่องไอพ่นเจ็ตในการบินทั้งหมด

เจ้าของสนามทราบว่าจะมีคนมาชมและเช่าเครื่องไอพ่นเจ็ตจำนวน C คน เขาต้องการคำนวณค่าเช่าเครื่องไอพ่นเจ็ตต่อคนที่น้อยที่สุด ที่จะทำให้เขาไม่ขาดทุน เพื่อให้การเช่าเป็นไปได้สะดวก ค่าเช่าจะต้องเป็นจำนวนเต็มเสมอด้วย

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

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็มบวก N และ M คั่นด้วยช่องว่าง แทนขนาดความกว้างและความยาวของสนาม (1 ≤ ≤ 100; 1 ≤ ≤ 100)

บรรทัดที่สองระบุจำนวนเต็มบวก L และ K คั่นด้วยช่องว่าง โดยที่ L แทนราคาเชื้อเพลิงต่อการบินหนึ่งครั้งและ K แทนจำนวนครั้งที่เครื่องไอพ่นใช้บินได้ต่อคนเช่าหนึ่งคน (1 
≤ ≤ 100; 1 ≤ ≤ 100)

บรรทัดที่สามระบุจำนวนเต็มบวก C แทนจำนวนผู้เล่นทั้งหมดที่เข้ามาเล่น (1 
≤ C < 1,000)

บรรทัดถัดไปอีก N บรรทัด แต่ละบรรทัดรับจำนวนเต็มบวก M ตัว แต่ละตัวถูกคั่นด้วยช่องว่าง แทนค่าไฟในแต่ละช่องที่ประดับไฟ ซึ่งจะเป็นจำนวนเต็มบวกที่มีค่าไม่เกิน 3,000

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

ที่มา
การแข่งขัน IOI Thailand League เดือนกันยายน 2553
โจทย์โดย: ธงชัย วิโรจน์ศักดิ์เสรี

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3 3
2 1
1
1 1 1
1 1 1
1 1 1
11
3 4
3 2
7
1 2 3 4
4 3 2 1
1 1 1 1
10

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

กำลังออนไลน์: 16 ผู้เยี่ยมชมและ 1 สมาชิก (0 บอท)