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 size`n`

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
```