Alice和Bob正在玩一个游戏。首先，Alice画一些包含N个顶点、M条弧的有向图；然后，Bob试图破坏它。在每一步，Bob可以从图中移去一个顶点，并且移去所有进入该顶点的弧或所有由该顶点发出的弧。在画图的时候，Alice给每个顶点赋予了两个权值：Wi+和Wi-。如果Bob移去所有进入第i个顶点的弧，则Bob需要支付Wi+美元给Alice；如果Bob移去所有由第i个顶点发出的弧，则Bob需要支付Wi-美元给Alice。计算Bob移去图中所有的弧，需要支付的最少费用。

输入文件包含多个测试数据。第1行是整数T，代表测试数据的数目。每个测试数据描述了Alice所画的一个有向图，格式为：第1行为两个整数N和M (1≤N≤100，1≤M≤5 000)；第2行为N个整数，代表每个顶点的权值Wi+；第3行也是N个整数，代表每个顶点的权值Wi-，所有的权值为正整数，不超过106；接下来有M行，每行为两个整数，这M行描述了有向图中的M条弧。有向图中可能包含回路和重边。

每个测试数据的输出之间用空行隔开。每个测试数据的第1行为W，表示Bob移去所有弧所需支付的最少费用。第2行为整数K，表示Bob走的步数。接下来输出K行，描述Bob的每一步，每一行首先是顶点的序号，然后是一个字符“+”或“-”，字符“+”表示Bob移去所有进入该顶点的弧，字符“-”表示Bob移去所有由该顶点发出的弧。