Description
有N幢大楼和M个避难所。第i大楼的坐标为(Xi,Yi),有Bi(1≤Bi≤1000)个人在里面工作,第i个避难所的容纳人数为Ci。位于(Xi,Yi)的大楼和位于(Pj,Qj)的避难所之间的时间为Di,j=∣Xi−Pj∣+∣Yi−Qj∣+1分钟。在理想情况下,某一大楼的所有工人都应跑向最近的避难所。然而,这将导致一些避难所过度拥挤,另一些避难所半空。为了解决这个问题,市议会制定了一个疏散计划,在该计划中指定了应该从大楼i到避难所j避难的人数Eij。判断所有人避难的所有时间的总和是不是最小。
第1行包含两个数字N和M(1≤N,M≤100)。下面的N行,每行都包含整数Xi、Yi和Bi,其中Xi、Yi(−1000≤Xi,Yi≤1000)是大楼的坐标,Bi(1≤Bi≤1000)是该大楼的工人人数。后面的M行,每行都包含三个整数Pj、Qj和Cj,其中Pi、Qi(−1000≤Pj,Qj≤1000)是避难所的坐标,Cj(1≤Cj≤1000)是该避难所的容量。市议会疏散计划的描述包括N行。每行都代表一个大楼的疏散计划(按照城市描述中给出的顺序)。第i个大楼的疏散计划包含M个整数Eij(0≤Eij≤1000),表示从第i个大楼疏散到第j个避难所的工人人数。输入文件中的计划保证有效。
Output
若市议会的计划是最优的,则给输出写一个单词“OPTIMAL”;否则在第1行输出“SUBOPTIMAL”;然后是N行,用与输入文件相同的格式描述计划。你的计划自身不一定是最优的,但必须是有效的,比市议会的计划更好。
Samples
3 4
-3 3 5
-2 -2 6
2 2 5
-1 1 3
1 1 4
-2 -2 7
0 -1 3
3 1 1 0
0 0 6 0
0 3 0 2
SUBOPTIMAL
3 0 1 1
0 0 6 0
0 4 0 1