Есть клетчатый квадрат размера \(n \times n\). Некоторые клетки квадрата покрашены в черный цвет, остальные клетки покрашены в белый. За одну операцию разрешается выбрать некоторый прямоугольник и перекрасить все его клетки в белый цвет. За перекраску прямоугольника размера \(h \times w\) взимается штраф в размере \(\min(h, w)\). Требуется за минимальный суммарный штраф покрасить все клетки в белый цвет.
Квадрат большой, поэтому зададим мы его в сжатом виде. Множество чёрных клеток является объединением \(m\) прямоугольников.
Выходные данные
Выведите одно число — минимальный суммарный штраф покраски всего квадрата в белый цвет.
Примечание
На картинке вы можете видеть два примера и некоторые из оптимальных способов их покрасить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 2
4 1 5 10
1 4 10 5
|
4
|
|
2
|
7 6
2 1 2 1
4 2 4 3
2 5 2 5
2 3 5 3
1 2 1 2
3 2 5 3
|
3
|