Destroying The Graph

Alice and Bob play the following game. First, Alice draws some directed graph with N vertices and M arcs. After that Bob tries to destroy it. In a move he may take any vertex of the graph and remove either all arcs incoming into this vertex, or all arcs outgoing from this vertex.
Alice assigns two costs to each vertex: Wi⁺ and Wi^-. If Bob removes all arcs incoming into the i-th vertex he pays Wi⁺ dollars to Alice, and if he removes outgoing arcs he pays Wi^- dollars.
Find out what minimal sum Bob needs to remove all arcs from the graph.

Input

Input file describes the graph Alice has drawn. The first line of the input file contains N and M (1 <= N <= 100, 1 <= M <= 5000). The second line contains N integer numbers specifying Wi⁺. The third line defines Wi^- in a similar way. All costs are positive and do not exceed 10⁶ . Each of the following M lines contains two integers describing the corresponding arc of the graph. Graph may contain loops and parallel arcs.

Output

On the first line of the output file print W --- the minimal sum Bob must have to remove all arcs from the graph. On the second line print K --- the number of moves Bob needs to do it. After that print K lines that describe Bob's moves. Each line must first contain the number of the vertex and then '+' or '-' character, separated by one space. Character '+' means that Bob removes all arcs incoming into the specified vertex and '-' that Bob removes all arcs outgoing from the specified vertex.

Sample Input

3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3

Sample Output

5

3

1 +

2 -

2 +

Source

Northeastern Europe 2003, Northern Subregion

题目类型：最小点权覆盖(最小割)

算法分析：每个点都有两个属性(删除入边的权值和删除出边的权值)，则拆点一个处理入边，一个处理出边，使得原图转化为二分图。对于给出的边<u, v>，从u向n+v连一条容量为INF的有向边，从源点向点1~n分别连一条容量为对应点出边点权的有向边，从点n~2n分别向汇点连一条容量为对应点入边点权的有向边。最后跑一个最大流就可得到最小费用值。最后从源点s开始dfs将在残余网络中在同一个连通分量中的点打上标记，所有1~n中没有标记的点就是选择删除出边的，n~2n中被标记的点就是选择删除入边的

Evacuation Plan

The City has a number of municipal buildings and a number of fallout shelters that were build specially to hide municipal workers in case of a nuclear war. Each fallout shelter has a limited capacity in terms of a number of people it can accommodate, and there's almost no excess capacity in The City's fallout shelters. Ideally, all workers from a given municipal building shall run to the nearest fallout shelter. However, this will lead to overcrowding of some fallout shelters, while others will be half-empty at the same time.

To address this problem, The City Council has developed a special evacuation plan. Instead of assigning every worker to a fallout shelter individually (which will be a huge amount of information to keep), they allocated fallout shelters to municipal buildings, listing the number of workers from every building that shall use a given fallout shelter, and left the task of individual assignments to the buildings' management. The plan takes into account a number of workers in every building - all of them are assigned to fallout shelters, and a limited capacity of each fallout shelter - every fallout shelter is assigned to no more workers then it can accommodate, though some fallout shelters may be not used completely.

The City Council claims that their evacuation plan is optimal, in the sense that it minimizes the total time to reach fallout shelters for all workers in The City, which is the sum for all workers of the time to go from the worker's municipal building to the fallout shelter assigned to this worker.

The City Mayor, well known for his constant confrontation with The City Council, does not buy their claim and hires you as an independent consultant to verify the evacuation plan. Your task is to either ensure that the evacuation plan is indeed optimal, or to prove otherwise by presenting another evacuation plan with the smaller total time to reach fallout shelters, thus clearly exposing The City Council's incompetence.

During initial requirements gathering phase of your project, you have found that The City is represented by a rectangular grid. The location of municipal buildings and fallout shelters is specified by two integer numbers and the time to go between municipal building at the location (Xi, Yi) and the fallout shelter at the location (Pj, Qj) is D_i,j = |Xi - Pj| + |Yi - Qj| + 1 minutes.

Input

The input consists of The City description and the evacuation plan description. The first line of the input file consists of two numbers N and M separated by a space. N (1 ≤ N ≤ 100) is a number of municipal buildings in The City (all municipal buildings are numbered from 1 to N). M (1 ≤ M ≤ 100) is a number of fallout shelters in The City (all fallout shelters are numbered from 1 to M).

The following N lines describe municipal buildings. Each line contains there integer numbers Xi, Yi, and Bi separated by spaces, where Xi, Yi (-1000 ≤ Xi, Yi ≤ 1000) are the coordinates of the building, and Bi (1 ≤ Bi ≤ 1000) is the number of workers in this building.

The description of municipal buildings is followed by M lines that describe fallout shelters. Each line contains three integer numbers Pj, Qj, and Cj separated by spaces, where Pi, Qi (-1000 ≤ Pj, Qj ≤ 1000) are the coordinates of the fallout shelter, and Cj (1 ≤ Cj ≤ 1000) is the capacity of this shelter.

The description of The City Council's evacuation plan follows on the next N lines. Each line represents an evacuation plan for a single building (in the order they are given in The City description). The evacuation plan of ith municipal building consists of M integer numbers E_i,j separated by spaces. E_i,j (0 ≤ E_i,j ≤ 1000) is a number of workers that shall evacuate from the i^th municipal building to the j^th fallout shelter.

The plan in the input file is guaranteed to be valid. Namely, it calls for an evacuation of the exact number of workers that are actually working in any given municipal building according to The City description and does not exceed the capacity of any given fallout shelter.

Output

If The City Council's plan is optimal, then write to the output the single word OPTIMAL. Otherwise, write the word SUBOPTIMAL on the first line, followed by N lines that describe your plan in the same format as in the input file. Your plan need not be optimal itself, but must be valid and better than The City Council's one.

Sample Input

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

Sample Output

SUBOPTIMAL

3 0 1 1

0 0 6 0

0 4 0 1

Source

Northeastern Europe 2002

题目类型：最小费用流(消圈)

算法分析：直接使用最小费用流算法得到的结果是正确的而且是最优方案，但是会TLE。由于本题没有要求最后求得的最终方案一定是最优的，这里使用费用流的消圈算法来求解。消圈定理描述为残余网络里若存在负费用圈，那么当前流不是最小费用流。负圈指的是费用总和为负且每条边剩余流量大于零的圈。若能够在原图中找到一个费用为负的圈的话，那么沿着这个圈流量增加1就能够在不改变原始总流量的基础上使得总费用变得更低，所以只要找到一个负圈即可，先按照输入构造残余网络，然后利用SPFA判断是否存在负圈，若存在负圈则沿着负圈上的点相应修改流量