Field for the Cemetery

I tried to solve this problem and I am getting WA on test 16. I would really apreciate your help.

I tried to find an upper bound of the solution.

I colored the matrix of size q x c in n colors so that every two neighbour cells have different colours and every continuous segment of sizen does not contain the same colour. For the example in the statement , I colour the matrix like that:

1 2 3 1 2
2 3 1 2 3
3 1 2 3 1
1 2 3 1 2

Now , my aproximation of the upper bound would be the minimum number of cells with some color. It is really close to the real solution and I am quite sure that it is the solution too.

Notice that for a matrix of n x c you have the same number of colors on every line. So , I got the following calculus formula: ans = ( q / n ) * c + (c / n) * (q % n) + corner where corner = (l%n) + (c%n) - n.

UPD: If the solution is equal with my upper bound , than how can you prove that the lower bound is equal with the upper bound ?

UPD2: I also tried to put the segments after some rule , but it didn't suceed. For example if you have 7 7 4 you might be tempted to place the segments something like this:

1 1 1 1 8 9 1
2 2 2 2 8 9 1
3 3 3 3 8 9 1
4 4 4 4 8 9 1
5 5 5 5 0 0 0
6 6 6 6 0 0 0
7 7 7 7 0 0 0

But they can be placed like this:

1 1 1 1 8 9 1
2 2 2 2 8 9 1
3 3 3 3 8 9 1
4 5 6 0 8 9 1
4 5 6 7 7 7 7
4 5 6 1 1 1 1
4 5 6 2 2 2 2