Evacuation Plan#4586
In the city, there are municipal buildings and bomb shelters constructed specifically for evacuating employees in the event of a nuclear war. Each bomb shelter has a limited capacity for the number of people it can accommodate. Ideally, all employees from a municipal building would go to the nearest bomb shelter. However, this could lead to some bomb shelters being overcrowded while others remain underutilized.
To address this issue, the City Council has developed a special evacuation plan. Instead of assigning each employee individually to a specific bomb shelter, the plan determines how many employees from each municipal building should go to each bomb shelter. The task of distributing individual employees is left to the internal management of each municipal building.
The evacuation plan takes into account the number of employees in each building, ensuring that every employee is included and that no bomb shelter exceeds its capacity.
The City Council claims that their evacuation plan is optimal, meaning that it minimizes the total evacuation time for all city employees.
The city mayor, who is often at odds with the City Council, is skeptical of this claim. He has hired you as an independent expert to verify the evacuation plan. Your task is to either confirm the optimality of the City Council's plan or to prove otherwise by providing an alternative evacuation plan with a shorter total evacuation time for all employees.
The city map can be represented by a square grid. The locations of municipal buildings and bomb shelters are specified by pairs of integers. The evacuation time from a municipal building at coordinates X_i, Y_i to a bomb shelter at coordinates P_j, Q_j is
minutes.
The input describes the city map and the evacuation plan proposed by the City Council.
The first line contains two integers (1 \le N \le 100) and (1 \le M \le 100), separated by a space. is the number of municipal buildings (numbered from to ), and is the number of bomb shelters (numbered from to ).
The next lines describe the municipal buildings. Each line contains integers X_i, Y_i, and B_i, separated by spaces, where X_i, Y_i (-1000 \le X_i, Y_i \le 1000) are the coordinates of the building, and B_i (1 \le B_i \le 1000) is the number of employees in the building.
The next lines describe the bomb shelters. Each line contains integers P_j, Q_j, and C_j, separated by spaces, where P_j, Q_j (-1000 \le P_j, Q_j \le 1000) are the coordinates of the bomb shelter, and C_j (1 \le C_j \le 1000) is the capacity of the bomb shelter.
The next lines describe the evacuation plan. Each line corresponds to a specific building and consists of integers E_{ij}, separated by spaces. Here, E_{ij} (0 \le E_{ij} \le 10000) is the number of employees scheduled to evacuate from the -th building to the -th bomb shelter.
It is guaranteed that the plan provided in the input is correct.
If the City Council's evacuation plan is optimal, output only the single word OPTIMAL.
Otherwise, output the word SUBOPTIMAL on the first line, and on the following lines, output your improved evacuation plan in the same format as was provided in the input. Your plan does not need to be optimal, but it must be better than the City Council's plan.
Example 1