Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Предприимчивый друг Геральта, краснолюд Золтан Хивай, решил остепениться и заняться недвижимостью в Новиграде. Помогите ему спланировать свою деятельность в городе наилучшим образом.
Прямоугольная сетка улиц разделяет Новиград на `N * M` кварталов, адреса которых задаются парами чисел `i, j`. Для каждого квартала известны доступная в нём для застройки площадь `s_{ij}` и стоимость строительства `c_{ij}`. Потратив `c_{ij}` крон, мы можем построить в квартале обычный дом и продать его за `s_{ij}^2` крон. Либо мы можем договориться с местными жителями, заплатив им `X` крон, перекрыть улицу и объединить пару соседних кварталов, построив на объединённом участке роскошную усадьбу. Если объединялись участки с площадями `s_1` и `s_2` и стоимостями строительства `c_1` и `c_2`, то общие затраты на постройку усадьбы будут равны `c_1 + c_2 + X` (с учётом стоимости перекрытия улицы для объединения участков), а стоимость продажи готовой усадьбы — `(s_1+s_2)^2`. Каждый квартал можно использовать не более одного раза: либо оставить незастроенным, либо построить на нём обычный дом, либо объединить его ровно с одним из четырёх соседних по стороне кварталов и построить одну усадьбу на объединённой территории.
Кроме того, для каждой постройки (неважно — дома или усадьбы) нужно получить разрешение от магистрата. Первое разрешение стоит `p_1`, второе — `p_2`, и так далее до `p_{N * M}` (`p_i <= p_{i+1}`). Для `k` построек общая стоимость разрешений составит `p_1+p_2+...+p_k`. Определите, какую максимальную сумму Золтан может выручить от продажи недвижимости за вычетом всех необходимых расходов, и выведите соответствующий план застройки.
В первой строке указаны `3` положительных целых числа `N`, `M` (`1 <= N * M <= 1000`) и `X` (`0 < X <= 10^9`).
Во второй строке указаны `N * M` неотрицательных целых чисел `p_i` в порядке неубывания (`0 <= p_i <= 10^9`, `p_i <= p_{i+1}`) — стоимости разрешений на строительство.
Затем следуют `N` строк по `M` неотрицательных целых чисел `s_{ij}` в каждой (`0 <= s_{ij} <= 10^5`) — площади кварталов.
А затем следуют ещё `N` строк по `M` неотрицательных целых чисел `c_{ij}` в каждой (`0 <= c_{ij} <= 10^9`) — стоимости строительства в каждом из кварталов.
В первой строке выведите два неотрицательных целых числа: `V` — максимальную сумму денег, которую можно получить от продажи недвижимости за вычетом необходимых расходов, и `K` — количество построек, при котором эта сумма достигается.
Далее выведите `K` строк, описывающих постройки: дома и усадьбы.
Дом должен описываться в виде `1` `i` `j` (`1 <= i <= N, 1<= j <= M`), где `(i, j)` —адрес квартала, в котором дом должен быть построен.
Усадьба должна описываться в виде `2` `i_1` `j_1` `i_2` `j_2` (`1 <= i_1, i_2 <= N, 1<= j_1,j_2 <= M`), где `(i_1, j_1)` и `(i_2, j_2)` —адреса кварталов, которые нужно объединить для постройки усадьбы.
Описания домов и усадеб можно выводить в любом порядке. Если квартал остаётся незастроенным, для него не нужно выводить ничего. Если существует несколько решений, максимизирующих общую прибыль, выведите любое из них.
```sample Пример ввода
2 3 5
0 0 2 2 3 10
6 1 7
4 5 3
1 9 9
0 4 2
```
```sample Пример вывода
197 3
1 2 2
2 1 1 2 1
2 1 3 2 3
```
Пояснение к примеру 1. Прибыль получается следующим образом:
* дом в квартале `(2, 2)`: площадь `5`, затраты `4`, первое разрешение на строительство бесплатное, чистая прибыль `25-4 = 21` крона.
* усадьба в кварталах `(1, 1)` и `(2, 1)`: общая площадь `6+4 = 10`, затраты `1 + 0 + 5=6`, второе разрешение также бесплатное, чистая прибыль `100 - 6 = 94`.
* усадьба в кварталах `(1, 3)` и `(2, 3)`: общая площадь `7+3 = 10`, затраты `9 + 2 +5=16`, разрешение на строительство `2` , чистая прибыль `100 - 16 - 2 = 82`.
Получаем общую прибыль `21 + 94 + 82 = 197` крон.
```sample Пример ввода
1 1 10
0
1
10
```
```sample Пример вывода
0 0
```
Пояснение к примеру 2. Никакое строительство не будет выгодным, поэтому оптимальный для Золтана вариант — не строить ничего и сохранить свои деньги.
Начало
Рабочее место участника
Максимальный поток минимальной стоимости