ZOJ Problem Set - 3616
Cici needs to set a new choir now. Here, there are n * m her classmates standing in the shape of a n * m rectangle. This time, we are prepareing to sing a song called "Cici's dream". Each of her classmate has an integer value to evaluate his/her ability on singing this song, and if he/she can not sing this song (if the singing ability is a negetive number, it means he/she can not sing this song), we are forbidden to choose him/her into our choir. Now, Cici wants to choose a sub-rectangle of her classmates to get a maximal sum of singing value, can you help Cici to get the maximal singing value?
In addition, it is required that there are at least b boys and at least g girls in the choir.
The input file consists of several test cases. The first line of each test case contains four integers n, m, b, g (0 < n <= 100, 0 < m <= 2000, 0 < b, g <= m * n), indicating a n * m rectangle, and b, g means there are at least b boys and g girls in the choir.
Then following n lines, each line contains m pairs of integers indicating the singing value of her classmate and the sex of her classmate ('1' stands for boy and '2' stands for girl). All singing values are less than 10000.
For each test case, print a number of the maximal sum of singing value Cici can get. If there is not a sub-rectangle, print "No solution!"
3 2 1 1 1 1 2 1 3 2 4 2 2 1 -1 2
Author: LI, Fei
Contest: ZOJ Monthly, June 2012