Matcom Online Grader

Fito y Ana están ocupados en el siguiente juego. Primero, Ana dibuja algún grafo dirigido de $N$ vértices y $M$ arcos . Después Fito trata de destruirlo. En una jugada él puede escoger un vértice del grafo y eliminar todas las aristas que entran o todas las que salen desde este vértice.

Ana le asigna un valor a cada vértice: $I_i$ y $O_i$. Si Fito elimina las aristas que entran al $i$-ésimo vértice él paga $I_i$ pesos a Ana, y si elimina las aristas que salen, entonces paga $O_i$ pesos.

Busca la menor suma de dinero que Fito debería pagar para remover todas las aristas del grafo.

Input

La entrada describe el grafo que Ana dibujó. La primera línea contiene dos enteros $N$ y $M$ ($1 \leq N \leq 100, 1 \leq M \leq 5000$). La segunda línea contiene $N$ enteros $I_i$ ($i = 1, …, N$). La tercera línea contiene $N$ enteros $O_i$ ($i = 1,…, N$) . Todos los costos son positivos y no exceden $10^6$. Cada una de las siguientes $M$ líneas contienen dos enteros describiendo los arcos del grafo. El grafo puede contener arcos paralelos y lazos.

Output

En la primera línea de la salida imprime $W$ – la menor suma de dinero que Fito debe pagar para remover todas las aristas del grafo. En la segunda línea imprima $K$ – el número de movimientos necesarios. Después siguen $K$ líneas que describen los movimientos de Fito. Cada línea debe contener el número del vértice y el carácter $\texttt{+}$ o $\texttt{-}$, separados por un espacio. El carácter $\texttt{+}$ significa que Fito elimina todos los arcos entrando al vértice especificado y $\texttt{-}$, que Fito elimina todos los arcos saliendo. Para un caso de prueba es posible múltiples soluciones, imprima cualquiera.

Sample test(s)