Problem: Thanks to the Doctor's help, the rebels managed to steal enough gold to launch a full-scale attack on the Empire! However, Darth Vader is looking for revenge and wants to take back his gold.

The rebels have hidden the gold in various bases throughout the galaxy. Darth Vader and the Empire are looking to send out their spaceships to attack these bases.

The galaxy can be represented as an undirected graph with n planets (nodes) and m wormholes (edges), each connecting two planets.

A total of s empire spaceships and b rebel bases are located at different planets in the galaxy.

Each spaceship is given a location x, denoting the index of the planet on which it is located, an attacking strength a, and a certain amount of fuel f.

Each base is given a location x, and a defensive strength d.

A spaceship can attack a base if both of these conditions hold: 

  * the spaceship's attacking strength is greater or equal than the defensive strength of the base 
  * the spaceship's fuel is greater or equal to the shortest distance, computed as the number of wormholes, between the spaceship's planet and the base's planet 



Vader is very particular about his attacking formations. He requires that each spaceship is to attack at most one base and that each base is to be attacked by at most one spaceship.

Vader knows that the rebels have hidden k gold in each base, so he will assign the spaceships to attack bases in such a way that maximizes the number of bases attacked.

Therefore, for each base that is attacked, the rebels lose k gold.

However, the rebels have the ability to create any number of dummy bases. With the Doctor's help, these bases would exist beyond space and time, so all spaceship can reach them and attack them. Moreover, a dummy base is designed to seem irresistible: that is, it will always be attacked by some spaceship.

Of course, dummy bases do not contain any gold, but creating such a dummy base costs h gold.

What is the minimum gold the rebels can lose if they create an optimal number of dummy bases?

Input

The first line contains two integers n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 10000), the number of nodes and the number of edges, respectively.

The next m lines contain two integers u and v (1 ≤ u, v ≤ n) denoting an undirected edge between the two nodes.

The next line contains four integers s, b, k and h (1 ≤ s, b ≤ 1000, 0 ≤ k, h ≤ 10^9), the number of spaceships, the number of bases, the cost of having a base attacked, and the cost of creating a dummy base, respectively.

The next s lines contain three integers x, a, f (1 ≤ x ≤ n, 0 ≤ a, f ≤ 10^9), denoting the location, attack, and fuel of the spaceship.

The next b lines contain two integers x, d (1 ≤ x ≤ n, 0 ≤ d ≤ 10^9), denoting the location and defence of the base.

Output

Print a single integer, the minimum cost in terms of gold.

Example

Input


6 7
1 2
2 3
3 4
4 6
6 5
4 4
3 6
4 2 7 3
1 10 2
3 8 2
5 1 0
6 5 4
3 7
5 2


Output


12

Note

One way to minimize the cost is to build 4 dummy bases, for a total cost of 4 × 3 = 12.

One empire spaceship will be assigned to attack each of these dummy bases, resulting in zero actual bases attacked.

Solution (in JAVA):

Solution:
//package com.company;
// Always comment out package when submitting.

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static class Task {

        public class SCCTarjan { // faster and shorter

            List<Integer>[] graph;
            boolean[] visited;
            Stack<Integer> stack;
            int time;
            int[] lowlink;
            List<List<Integer>> components;

            public List<List<Integer>> scc(List<Integer>[] graph) {
                int n = graph.length;
                this.graph = graph;
                visited = new boolean[n];
                stack = new Stack<>();
                time = 0;
                lowlink = new int[n];
                components = new ArrayList<>();

                for (int u = 0; u < n; u++)
                    if (!visited[u])
                        dfs(u);

                return components;
            }

            void dfs(int u) {
                lowlink[u] = time++;
                visited[u] = true;
                stack.add(u);
                boolean isComponentRoot = true;

                for (int v : graph[u]) {
                    if (!visited[v])
                        dfs(v);
                    if (lowlink[u] > lowlink[v]) {
                        lowlink[u] = lowlink[v];
                        isComponentRoot = false;
                    }
                }

                if (isComponentRoot) {
                    List<Integer> component = new ArrayList<>();
                    while (true) {
                        int x = stack.pop();
                        component.add(x);
                        lowlink[x] = Integer.MAX_VALUE;
                        if (x == u)
                            break;
                    }
                    components.add(component);
                }
            }
        }

        public class MaxFlowDinic { // O(V^2 * E)
            List<Edge>[] graph;
            public MaxFlowDinic(int nodes) {
                graph = createGraph(nodes);
            }

            class Edge {
                int t, rev;
                long cap, f;

                public Edge(int t, int rev, long cap) {
                    this.t = t;
                    this.rev = rev;
                    this.cap = cap;
                }
            }

            public List<Edge>[] createGraph(int nodes) {
                List<Edge>[] graph = new List[nodes];
                for (int i = 0; i < nodes; i++)
                    graph[i] = new ArrayList<>();
                return graph;
            }

            public void addEdge(int s, int t, long cap) {
//                if (cap == -Integer.MAX_VALUE / 3) cap = -Long.MAX_VALUE / 3;
                graph[s].add(new Edge(t, graph[t].size(), cap));
                graph[t].add(new Edge(s, graph[s].size() - 1, 0));
            }

            boolean dinicBfs(int src, int dest, int[] dist) {
                Arrays.fill(dist, -1);
                dist[src] = 0;
                int[] Q = new int[graph.length];
                int sizeQ = 0;
                Q[sizeQ++] = src;
                for (int i = 0; i < sizeQ; i++) {
                    int u = Q[i];
                    for (Edge e : graph[u]) {
                        if (dist[e.t] < 0 && e.f < e.cap) {
                            dist[e.t] = dist[u] + 1;
                            Q[sizeQ++] = e.t;
                        }
                    }
                }
                return dist[dest] >= 0;
            }

            long dinicDfs(int[] ptr, int[] dist, int dest, int u, long f) {
                if (u == dest)
                    return f;
                for (; ptr[u] < graph[u].size(); ++ptr[u]) {
                    Edge e = graph[u].get(ptr[u]);
                    if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
                        long df = dinicDfs(ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
                        if (df > 0) {
                            e.f += df;
                            graph[e.t].get(e.rev).f -= df;
                            return df;
                        }
                    }
                }
                return 0;
            }

            public long maxFlow(int src, int dest) {
                long flow = 0;
                int[] dist = new int[graph.length];
                while (dinicBfs(src, dest, dist)) {
                    int[] ptr = new int[graph.length];
                    while (true) {
                        long df = dinicDfs(ptr, dist, dest, src, Long.MAX_VALUE);
                        if (df == 0)
                            break;
                        flow += df;
                    }
                }
                return flow;
            }
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] graph = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Integer.MAX_VALUE / 2;
                }
                graph[i][i] = 0;
            }
            for (int i = 0; i < m; i++) {
                int a = sc.nextInt() - 1;
                int b = sc.nextInt() - 1;
                graph[a][b] = graph[b][a] = 1;
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        if (graph[j][k] > graph[j][i] + graph[i][k]) {
                            graph[j][k] = graph[j][i] + graph[i][k];
                        }
                    }
                }
            }
            int s = sc.nextInt();
            int b = sc.nextInt();
            int k = sc.nextInt();
            int[][] sp = new int[s][6];
            for (int i = 0; i < s; i++) {
                for (int j = 0; j < 4; j++) {
                    sp[i][j] = sc.nextInt();
                }
                sp[i][4] = i;
                sp[i][0] -= 1;
            }
            int[][] ba = new int[b][3];
            for (int i = 0; i < b; i++) {
                for (int j = 0; j < 3; j++) {
                    ba[i][j] = sc.nextInt();
                }
                ba[i][0] -= 1;
            }
            int[][] dirEdge = new int[k][2];
//            List<Integer>[] takeGraph = new List[n];
            for (int i = 0; i < k; i++) {
                int a = sc.nextInt() - 1;
                int r = sc.nextInt() - 1;
//                takeGraph[a].add(r);
                dirEdge[i] = new int[]{a, r};
            }
            int[] curValue = new int[n];
            Arrays.fill(curValue, -Integer.MAX_VALUE / 3);
            Arrays.sort(sp, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1] - o2[1];
                }
            });
            Arrays.sort(ba, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1] - o2[1];
                }
            });
            int spIdx = 0, baIdx = 0;
            while (spIdx < s) {
                while (baIdx < b && ba[baIdx][1] <= sp[spIdx][1]) {
                    curValue[ba[baIdx][0]] = Math.max(curValue[ba[baIdx][0]], ba[baIdx][2]);
                    baIdx++;
                }
                int bestPrice = -Integer.MAX_VALUE / 3;
                for (int i = 0; i < n; i++) {
                    if (graph[i][sp[spIdx][0]] <= sp[spIdx][2]) {
                        bestPrice = Math.max(bestPrice, curValue[i]);
                    }
                }
                sp[spIdx++][5] = bestPrice;
            }
            Arrays.sort(sp, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[4] - o2[4];
                }
            });
            int estimatedNodes = 2;
            Set<Integer> pos = new HashSet<>();
            Set<Integer> neg = new HashSet<>();
            Set<Integer>[] posToNeg = new Set[s];
            long[] weight = new long[s];
            for (int i = 0; i < s; i++) {
                if (sp[i][5] == -Integer.MAX_VALUE / 3) {
                    weight[i] = -Long.MAX_VALUE / 3;
                } else {
                    weight[i] = sp[i][5] - sp[i][3];
                }
            }
            for (int i = 0; i < s; i++) {
                posToNeg[i] = new HashSet<>();
            }
            for (int i = 0; i < k; i++) {
                int a = dirEdge[i][0];
                int r = dirEdge[i][1];
                if (weight[a] >= 0 && weight[r] < 0) {
                    pos.add(a);
                    neg.add(r);
                    posToNeg[a].add(r);
                }
            }
            estimatedNodes += pos.size();
            estimatedNodes += neg.size();
            Map<Integer, Integer> posMap = new HashMap<>();
            Map<Integer, Integer> negMap = new HashMap<>();
            int idx = 1;
            for (int p : pos) {
                posMap.put(p, idx++);
            }
            for (int nn: neg) {
                negMap.put(nn, idx++);
            }
            MaxFlowDinic mfd = new MaxFlowDinic(estimatedNodes);
            for (int p: pos) {
                int ii = posMap.get(p);
                mfd.addEdge(0, ii, weight[p]);
            }
            for (int nn: neg) {
                int ii = negMap.get(nn);
                mfd.addEdge(ii, idx, -weight[nn]);
            }
            for (int p = 0; p < posToNeg.length; p++) {
                for (int nn: posToNeg[p]) {
                    int ii = posMap.get(p);
                    int jj = negMap.get(nn);
                    mfd.addEdge(ii, jj, Long.MAX_VALUE / 3);
                }
            }
            long mcut = -mfd.maxFlow(0, idx);
            for (long w: weight) {
                if (w >= 0) mcut += w;
            }
            pw.println(mcut);
//            List<List<Integer>> sccComponents = new SCCTarjan().scc(takeGraph);
//            int[] idxToNew = new int[n];
//            long[] weights = new long[sccComponents.size()];
//            Set<Integer>[] outEdges = new Set[sccComponents.size()];
//            Set<Integer>[] inEdges = new Set[sccComponents.size()];
//            for (int i = 0; i < outEdges.length; i++) {
//                outEdges[i] = new HashSet<>();
//                inEdges[i] = new HashSet<>();
//            }
//            for (int i = 0; i < sccComponents.size(); i++) {
//                for (int v: sccComponents.get(i)) {
//                    idxToNew[v] = i;
//                    if (sp[v][5] == -Integer.MAX_VALUE / 3) {
//                        weights[i] += -Long.MAX_VALUE / 3;
//                    } else {
//                        weights[i] += sp[v][5] - sp[v][2];
//                    }
//                }
//            }
//            for (int i = 0; i < sccComponents.size(); i++) {
//                for (int v: sccComponents.get(i)) {
//                    outEdges[i].add(idxToNew[v]);
//                    inEdges[idxToNew[v]].add(i);
//                }
//            }
//            int estimateNodes = 0;
//            for (int i = 0; i < sccComponents.size(); i++) {
//                if (outEdges[i].size() > 0 && weights[i] > 0)
//            }


        }
    }

    // template, actual code is in class Task.
    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("class_treasurer.txt"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));

        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
//        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
//        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    // Faster IO with BufferedReader wrapped with Scanner
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}