Вы получили сетку размером \(n\times m\) от таинственного источника. Источник также дал вам волшебную целую положительную константу \(k\).
Источник сказал вам покрасить сетку некоторыми цветами, удовлетворяя следующее условие:
- Если \((x_1,y_1)\), \((x_2,y_2)\) — это две различные клетки одинакового цвета, то \(\max(|x_1-x_2|,|y_1-y_2|)\ge k\).
Вам не нравится использовать слишком много цветов. Пожалуйста, найдите минимальное количество цветов, необходимое для раскрашивания сетки.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество цветов, необходимое, чтобы покрасить сетку.
Примечание
В первом наборе входных данных одной из оптимальных конструкций является:
Во втором наборе входных данных цвета всех ячеек должны быть попарно различными, поэтому ответ — \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 3 2
5 1 10000
7 3 4
3 2 7
8 9 6
2 5 4
|
4
5
12
6
36
8
|