대피 계획

도시에는 여러 개의 관공서 건물과, 핵전쟁에 대비해 공무원을 대피시키려고 지은 여러 개의 방공호가 있다. 각 방공호가 수용할 수 있는 인원은 제한되어 있고, 도시 전체로 보아도 여유 공간이 거의 없다. 모든 근무자가 무작정 가장 가까운 방공호로 달려간다면, 어떤 방공호는 넘치고 다른 방공호는 절반만 차게 된다.

이를 막기 위해 시의회는 대피 계획을 세웠다. 근무자를 한 명씩 방공호에 배정하는 대신, 각 건물마다 그 건물의 근무자 몇 명이 어느 방공호로 갈지를 정한다. 계획이 유효(valid)하다는 것은 다음을 뜻한다.

• 모든 건물의 모든 근무자가 어떤 방공호에 배정되고,
• 어떤 방공호에도 그 수용 인원을 초과하는 근무자가 배정되지 않는다(방공호가 일부만 채워져도 된다).

시의회는 자신들의 계획이 최적(optimal)이라고 주장한다. 즉, 유효한 모든 계획 중에서 방공호까지 가는 데 걸리는 총 시간을 최소화한다는 것이다. 총 시간이란 모든 근무자에 대해, 각 근무자의 건물에서 그 근무자가 배정된 방공호까지 가는 시간을 모두 더한 값이다.

도시는 직사각형 격자로 나타낸다. 위치 $(X_i, Y_i)$의 관공서 건물과 위치 $(P_j, Q_j)$의 방공호 사이의 이동 시간은 다음과 같다.

$D_{i,j} = |X_i - P_j| + |Y_i - Q_j| + 1 \text{ (분)}$

도시의 배치와 시의회의 계획이 주어질 때, 이 계획이 정말로 최적인지 판별하라.

첫 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $N$ ($1 \le N \le 100$)은 관공서 건물의 수이며, 건물은 $1$번부터 $N$번까지 번호가 매겨진다. $M$ ($1 \le M \le 100$)은 방공호의 수이며, 방공호는 $1$번부터 $M$번까지 번호가 매겨진다.

이어지는 $N$개의 줄은 건물을 나타낸다. $i$번째 줄에는 세 정수 $X_i$, $Y_i$, $B_i$가 주어진다. $X_i, Y_i$ ($-1000 \le X_i, Y_i \le 1000$)는 건물의 좌표이고, $B_i$ ($1 \le B_i \le 1000$)는 그 건물의 근무자 수이다.

그다음 $M$개의 줄은 방공호를 나타낸다. $j$번째 줄에는 세 정수 $P_j$, $Q_j$, $C_j$가 주어진다. $P_j, Q_j$ ($-1000 \le P_j, Q_j \le 1000$)는 방공호의 좌표이고, $C_j$ ($1 \le C_j \le 1000$)는 그 방공호의 수용 인원이다.

마지막 $N$개의 줄은 시의회의 계획을 건물 순서대로 한 줄에 하나씩 나타낸다. $i$번째 줄에는 $M$개의 정수 $E_{i,1}, \dots, E_{i,M}$ ($0 \le E_{i,j} \le 1000$)가 주어지며, $E_{i,j}$는 건물 $i$에서 방공호 $j$로 대피하는 근무자 수이다.

주어지는 계획은 항상 유효하다. 즉, 각 건물 $i$에서 정확히 $B_i$명을 대피시키고, 어떤 방공호의 수용 인원도 초과하지 않는다.

시의회의 계획이 방공호까지 가는 총 시간을 최소화한다면 OPTIMAL을 출력한다. 그렇지 않다면, 즉 총 시간이 더 작은 유효한 계획이 존재한다면 SUBOPTIMAL을 출력한다.