План эвакуации
В городе есть муниципальные здания и бомобоубежища, которые были специально построены для эвакуации служащих в случае ядерной войны. Каждое бомбоубежище имеет ограниченную вместительность по количеству людей, которые могут в нем находиться. В идеале все работники из одного муниципального здания должны были бы бежать к ближайшему бомбоубежищу. Однако, в таком случае, некоторые бомбоубежища могли бы переполниться, в то время как остальные остались бы наполовину пустыми.
Чтобы резрешить эту проблему Городской Совет разработал специальный план эвакуации. Вместо того, чтобы каждому служащему индивидуально приписать, в какое бомбоубежище он должен бежать, для каждого муниципального здания определили, сколько служащих из него в какое бомобоубежище должны бежать. Задача индивидуального распределения была переложена на внутреннее управление муниципальных зданий.
План эвакуации учитывает количество служащих в каждом здании — каждый служащий должен быть учтен в плане и в каждое бомбоубежище может быть направлено количество служащих, не превосходящее вместимости бомбоубежища.
Городской Совет заявляет, что их план эвакуации оптимален в том смысле, что суммарное время эвакуации всех служащих города минимально.
Мэр города, находящийся в постоянной конфронтации с Городским Советом, не слишком то верит этому заявлению. Поэтому он нанял Вас в качестве независимого эксперта для проверки плана эвакуации. Ваша задача состоит в том, чтобы либо убедиться в оптимальности плана Городского Совета, либо доказать обратное, представив в качестве доказательства другой план эвакуации с меньшим суммарным временем для эвакуации всех служащих.
Карта города может быть представлена в виде квадратной сетки. Расположение муниципальных зданий и бомбоубежищ задается парой целых чисел, а время эвакуации из муниципального здания с координатами (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 строках выведите Ваш план эвакуации (более оптимальный) в том же формате, что и во входном файле. Ваш план не обязан быть оптимальным, но должен быть лучше плана Городского Совета.