План евакуації
У місті є муніципальні будівлі та бомобосховища, які були спеціально збудовані для евакуації службовців у випадку ядерної війни. Кожне бомбосховище має обмежену місткість по кілбкості людей, які можуть у ньому знаходитись. В ідеалі усі робітники з одного муніципального будинку повинні бул б бігти до найближчого бомбосховища. Проте, у такому випадку, деякі бомбосховща могли б переповнитись, у той час як інші залишились би наполовину порожніми.
Щоб розв'язати цю проблему Міська Рада розробила спеціальний план евакуації. Замість того, щоб кожному службовцю індивідуально прописати, у яке бомбосховище він повинен бігти, для кожного муніципального будинку визначили, скільки службовців з нього у яке бомобосховище повинні бігти. Задача індивідуального розподілу була перекладена на внутрішнє управлінння муніципальних будівель.
План евакуації враховує кількість службовців у кожному будинку — кожен службовець повинен бути врахований у плані і у кожне бомбосховище може бути направлена кількість службовців, яка не перевищує місткість бомбосховища.
Міська Рада заявляє, що їхній план евакуації оптимальний у тому змісті, що сумарний час евакуації усіх службовців міста мінімальний.
Мер міста, яки знаходиться у постійній конфронтації з Міською Радою, не дуже то вірить цій заяві. Тому він найняв Вас у якості незалежного експерта для перевірки плану евакуації. Ваша задача полягає у тому, щоб або переконатись в оптимальності плана Міської Ради, або довестиь протилежне, подавши у якості доказу інший план евакуації з меншим сумарним часом для евакуації усіх службовців.
Карта міста може бути подана у вигляді квадратної сітки. Розміщення муніципальних будівель та бомбосховищ задається парою цілих чисел, а час евакуації з муніципального будинку з координатами (X_i, Y_i) у бомбосховище з координатами (P_j, Q_j ) складає Dij = |X_i-P_j| + |Yi-Q_j| + 1 хвилин.
Вхідні дані
Вхідний файл містить опис карти міста та плану евакуації, запропонованого Міською Радою. Перший рядок вхідного файлу містить два цілих числа N (1 ≤ N ≤ 100) та M (1 ≤ M ≤ 100), відокремлених пропуском. N — число муніципальних будівель у місті (усі вони пронумеровані числами від 1 до N), M — число бомбосховищ (усі вони пронумеровані числами від 1 до M).
Наступні N рядків містять опис муніципальних будівель. Кожен рядок містить цілі числа X_i, Y_i та B_i, відокремлені пропусками, де X_i, Y_i (-1000 ≤ X_i, Y_i ≤ 1000) — координати будівель, а B_i (1 ≤ B_i ≤ 1000) — число службовців у будівлі.
Опис бомбосховищ міститься у наступних M рядках. Кожен рядок містить цілі числа P_j, Q_j та C_j, відокремлені пропусками, де P_j, Q_j (-1000 ≤ P_j, Q_j ≤ 1000) — координати бомбосховища, а C_j (1 ≤ C_j ≤ 1000) — місткість бомбосховища.
У наступних N рядках міститься опис плану евакуації. Кожен рядок являє собою опис плану евакуації для окремої будівлі. План евакуації з i-ї будівлі складається з M цілих чисел E_ij, відокремлених пропусками. E_ij (0 ≤ E_ij ≤ 10000) — кількість службовців, які повинні евакуюватись з i-ї будівлі у j-те бомбосховище.
Гарантиується, що план, заданий у вхідному файлі, коректний.
Вихідні дані
Якщо план евакуації Міської Ради оптимальний, то виведіть одне слово OPTIMAL. У протилежному випадку виведіть у першому рядку слово SUBOPTIMAL, а у наступних N рядках виведіть Ваш план евакуації (більш оптимальний) у тому ж форматі, що і у вхідному файлі. Ваш план не зобов'язаний бути оптимальним, але повинен бути кращим плану Міської Ради.