题目描述

Alice和Bob玩一个游戏。首先，Alice画一个有向图，包含$N$个顶点和$M$条弧。之后，Bob尝试破坏这个图。每次操作中，Bob可以选择任意一个顶点，并删除该顶点的所有入边或所有出边。

Alice为每个顶点设定了两个成本值：$W_i^+$和$W_i^-$。如果Bob删除第$i$个顶点的所有入边，他需要支付$W_i^+$美元；如果删除所有出边，则需要支付$W_i^-$美元。

要求计算Bob删除图中所有弧的最小总成本，并输出操作步骤。

输入格式

输入文件描述Alice所画的有向图。
第一行包含$N$和$M$（$1 \leq N \leq 100$，$1 \leq M \leq 5000$）。
第二行包含$N$个整数，表示$W_i^+$。
第三行包含$N$个整数，表示$W_i^-$。
所有成本均为正数且不超过$10^6$。
接下来的$M$行，每行包含两个整数，描述一条有向弧。图中可能包含自环和平行边。

输出格式

第一行输出$W$——Bob删除所有弧的最小总成本。
第二行输出$K$——Bob需要的操作次数。
接下来的$K$行，每行描述一个操作，包含顶点编号和'+'或'-'字符，用空格分隔。'+'表示删除该顶点的所有入边，'-'表示删除所有出边。

示例输入1

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

示例输出1

5
3
1 +
2 -
2 +

来源

Northeastern Europe 2003, Northern Subregion