План евакуації#4586

План евакуації

2 секунди

64 мегабайти

Дуже складна

У місті є муніципальні будівлі та бомбосховища, збудовані спеціально для евакуації службовців у разі ядерної війни. Кожне бомбосховище має обмежену місткість щодо кількості людей, які можуть у ньому перебувати. В ідеалі всі працівники з однієї муніципальної будівлі мали б іти до найближчого бомбосховища, але це могло б призвести до переповнення деяких сховищ, тоді як інші залишалися б недозавантаженими.

Щоб вирішити цю проблему, Міська Рада розробила спеціальний план евакуації. Замість того, щоб кожного службовця індивідуально призначати до конкретного бомбосховища, у плані визначено, скільки службовців із кожної муніципальної будівлі має йти до кожного бомбосховища. Завдання розподілу поіменно залишено внутрішній адміністрації будівель.

План евакуації враховує кількість службовців у кожній будівлі, гарантуючи, що всі охоплені, і жодне бомбосховище не перевищить своєї місткості.

Міська Рада стверджує, що їхній план евакуації оптимальний, тобто мінімізує загальний час евакуації для всіх працівників міста.

Міський голова, який часто має суперечки з Міською Радою, сумнівається у цій заяві. Він найняв вас як незалежного експерта перевірити план евакуації. Ваше завдання — або підтвердити оптимальність плану Міської Ради, або спростувати її, представивши альтернативний план евакуації з меншим загальним часом евакуації.

Мапу міста можна уявити як квадратну сітку. Місця муніципальних будівель і бомбосховищ задаються парами цілих чисел. Час евакуації із будівлі з координатами $X_{i}$ X_i, $Y_{i}$ Y_i до бомбосховища з координатами $P_{j}$ P_j, $Q_{j}$ Q_j обчислюється так:

D_{ij} = ∣ X_{i} - P_{j} ∣ + ∣ Y_{i} - Q_{j} ∣ + 1

D_{ij} = |X_i - P_j| + |Y_i - Q_j| + 1

хвилин.

Вхідні дані

У вхідних даних описується карта міста та план евакуації, запропонований Міською Радою.

Перший рядок містить два цілі числа $N$ ( $1 \leq N \leq 100$ 1 \le N \le 100) і $M$ ( $1 \leq M \leq 100$ 1 \le M \le 100), розділені пробілом. $N$ — кількість муніципальних будівель (нумеруються від $1$ до $N$ ), $M$ — кількість бомбосховищ (нумеруються від $1$ до $M$ ).

Наступні $N$ рядків описують муніципальні будівлі. Кожен рядок містить $X_{i}$ X_i, $Y_{i}$ Y_i і $B_{i}$ B_i ( $- 1000 \leq X_{i}, Y_{i} \leq 1000$ -1000 \le X_i, Y_i \le 1000 — координати будівлі, $1 \leq B_{i} \leq 1000$ 1 \le B_i \le 1000 — кількість службовців у будівлі).

Далі йдуть $M$ рядків — опис бомбосховищ: у кожному рядку $P_{j}$ P_j, $Q_{j}$ Q_j ( $- 1000 \leq P_{j}, Q_{j} \leq 1000$ -1000 \le P_j, Q_j \le 1000) — координати сховища, $C_{j}$ C_j ( $1 \leq C_{j} \leq 1000$ 1 \le C_j \le 1000) — місткість сховища.

Наступні $N$ рядків описують план евакуації: кожен рядок відповідає будівлі та містить $M$ чисел $E_{ij}$ E_{ij} ( $0 \leq E_{ij} \leq 10000$ 0 \le E_{ij} \le 10000) — скільки осіб із $i$ -ї будівлі мають йти до $j$ -го бомбосховища.

Гарантується, що план у вхідних даних коректний.

Вихідні дані

Якщо план Міської Ради оптимальний, виведіть лише слово OPTIMAL.

Інакше спочатку виведіть SUBOPTIMAL, а далі $N$ рядків — ваш покращений план у тому ж форматі. Ваш план не обов'язково має бути оптимальним, але має бути кращим за початковий план.

Приклади

Приклад 1