Problem: Problem I: Train King

Roland has been given a mission of dangerous material transfer by Train King. The material is stored in the station A and subject to being transferred to the station B. He will bring it by direct trains between A and B, one (or zero) unit per ride.

Your task is to write a program to find out the most optimal way of his bringing. Your program will receive the timetable of trains on the mission day and should report how many units of material can be transferred at the end. Be aware that there can be trains which can go to the past time or the same time which train leaved the station.

Each train consists of one or more cars. Roland is disallowed to ride the same car of the same train multiple times. This restriction avoids time paradox. He is still allowed to get on a different car, though. You can assume he can change trains instantly.



Input

The first line contains two integers NAB and NBA (0 <= NAB, 0 <= NBA and NAB + NBA <= 50). NAB denotes the number of trains from A to B; NBA denotes the number from B to A.

The next NAB lines describe the information about trains from A to B. Each line gives the information of one train with three integers Ci, Di and Ai (1 <= Ci <= 10, 0 <= Di, Ai < 86400) : the number of cars, the departure time, and the arrival time.

The next NBA lines describe the information about trains from B to A. The information is given in the same format.

Output

Print the maximum amount, in units, of dangerous material that can be transferred.

Examples

Input

1 1
10 100 0
10 100 0


Output

10


Input

5 5
10 0 100
10 200 300
10 400 500
10 600 700
10 800 900
10 100 200
10 300 400
10 500 600
10 700 800
10 900 1000


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>


#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

const int INF = 1L << 30;
typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline void print_vec(const std::vector<T> &v) { for (int i = 0; i < v.size(); ++i) {  if (i != 0) {std::cout << " ";} std::cout << v[i];} std::cout << "\n"; }
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); }



class CostScalingPushRelabel {
public:
    struct Edge {
        const int from;
        const int to;       // 行き先のノード番号
        const int rev;      // 逆辺のindex. graph[to][rev]でアクセスできる
        int flow;           // 流量
        const int capacity; // 容量
        const int cost;     // cost
        const bool is_rev;  // 逆辺かどうか
        Edge(int from, int to, int rev, int flow, int capacity, int cost, bool is_rev) : from(from), to(to), rev(rev), flow(flow), capacity(capacity), cost(cost), is_rev(is_rev) {}
    };

    struct Node {
        int height = 0;
        int excessFlow = 0;  // 残存量
        double potential = 0;   // ポテンシャル
        Node(int height, int excessFlow, int potential) : height(height), excessFlow(excessFlow), potential(potential) {}
    };

    int numOfNode;
    std::vector<Node> nodeList;
    std::vector<std::vector<Edge>> graph;
    std::queue<int> active_nodes;
    int epsilon = 1;
    int SCALING_FACTOR = 2;
    int COST_SCALING_FACTOR = 1;

    CostScalingPushRelabel(unsigned int numOfNode) : numOfNode(numOfNode), COST_SCALING_FACTOR(2 * numOfNode) {
        for (int i = 0; i < numOfNode; ++i) {
            nodeList.emplace_back(Node(0, 0, 0));
        }
        graph.resize(numOfNode);
    }

    void add_edge(int from, int to, int capacity, int cost) {
        graph[from].emplace_back(Edge(from, to, (int) graph[to].size(), 0, capacity, cost, false));
        graph[to].emplace_back(Edge(to, from, (int) graph[from].size() - 1, capacity, capacity, -cost, true));
        epsilon = std::max(epsilon, abs(cost) * COST_SCALING_FACTOR);
    }

    // sourceからsinkへの最大流を求める
    // flowを流せること前提
    int minimum_cost_flow(const int source, const int sink, const int flow) {

        nodeList.at(source).excessFlow = flow;
        nodeList.at(sink).excessFlow = -flow;

        while (epsilon > 1.0) {
            for (int u = 0; u < numOfNode; ++u) {
                for (int v = 0; v < graph.at(u).size(); ++v) {
                    Edge &edge = graph.at(u).at(v);
                    if (edge.is_rev) {
                        continue;
                    }
                    const double reduced_cost = calc_reduced_cost(edge);
                    if (reduced_cost < 0) {
                        if (edge.capacity - edge.flow > 0) {
                            int f = edge.capacity - edge.flow;
                            push_flow(edge, f);
                        }
                    }
                    if (reduced_cost > 0) {
                        if (edge.flow > 0) {
                            int f = -graph.at(u).at(v).flow;
                            push_flow(edge, f);
                        }
                    }
                }
            }

            get_active_nodes();
            while (not active_nodes.empty()) {
                int node = active_nodes.front();
                active_nodes.pop();

                while (nodeList.at(node).excessFlow > 0) {
                    if (not push(node)) {
                        relabel(node);
                        active_nodes.push(node);
                        break;
                    }
                }
            }

            epsilon = std::max(1, epsilon / SCALING_FACTOR);
        }

        double total_cost = 0;
        for (int u = 0; u < numOfNode; ++u) {
            for (int v = 0; v < graph.at(u).size(); ++v) {
                Edge &edge = graph.at(u).at(v);
                if (edge.is_rev) {
                    continue;
                }
                total_cost += edge.flow * edge.cost;
            }
        }

        return total_cost;
    }

private:

    void print() {
        for (int u = 0; u < graph.size(); ++u) {
            for (int v = 0; v < graph.at(u).size(); ++v) {
                const Edge &edge = graph.at(u).at(v);
                if (edge.is_rev) {
                    continue;
                }
                std::cout << edge.from << " -> " << edge.to << "(" << edge.flow << ")" << std::endl;
            }
        }

        std::cout << "excess: ";
        for (int u = 0; u < nodeList.size(); ++u) {
            std::cout << u << ":" << nodeList[u].excessFlow << ", ";
        }
        std::cout << std::endl;
        std::cout << "potential: ";
        for (int u = 0; u < nodeList.size(); ++u) {
            std::cout << u << ":" << nodeList[u].potential << ", ";
        }
        std::cout << std::endl;
    }

    void push_flow(Edge &edge, int flow) {
        edge.flow += flow;
        graph.at(edge.to).at(edge.rev).flow -= flow;
        nodeList.at(edge.from).excessFlow -= flow;
        nodeList.at(edge.to).excessFlow += flow;
    }

    double calc_reduced_cost(const Edge &edge) {
        return edge.cost * COST_SCALING_FACTOR - nodeList.at(edge.from).potential + nodeList.at(edge.to).potential;
    }

    // activeな頂点を取得
    void get_active_nodes() {
        for (int u = 0; u < nodeList.size(); ++u) {
            if (nodeList[u].excessFlow > 0) {
                active_nodes.push(u);
            }
        }
    }

    // fromノードから他のノードにpushする
    bool push(const int from) {
        if (nodeList.at(from).excessFlow == 0) {
            return false;
        }
        assert(nodeList.at(from).excessFlow > 0);

        for (int i = graph.at(from).size() - 1; i >= 0; --i) {
            Edge &edge = graph.at(from).at(i);
            const int to = edge.to;
            if (edge.flow == edge.capacity) { continue; }
            const double reduced_cost = calc_reduced_cost(edge);

            if (reduced_cost < 0) {
                int flow = std::min(edge.capacity - edge.flow, nodeList[from].excessFlow);
                push_flow(edge, flow);

                if (nodeList.at(edge.to).excessFlow > 0 and nodeList.at(edge.to).excessFlow <= flow) {
                    active_nodes.push(edge.to);
                }
                return true;
            }
        }
        return false;
    }

    // fromのpotentialを修正
    void relabel(const int from) {
        double min_potential = INT_MAX;
        for (const Edge &edge : graph.at(from)) {
            if (edge.capacity - edge.flow > 0) {
                min_potential = std::min(min_potential, edge.cost * COST_SCALING_FACTOR + nodeList[edge.to].potential + epsilon);
            }
        }
        assert(min_potential != INT_MAX);
        nodeList[from].potential = min_potential;
    }

};

class Dinic {

public:
    struct Edge {
        const int to;         // 行き先のノードid
        long long flow;       // 流量
        const long long cap;  // 容量
        const int rev;        // 逆辺のノードid
        const bool is_rev;    // 逆辺かどうか
        Edge(int to, long long flow, long long cap, int rev, bool is_rev) : to(to), flow(flow), cap(cap), rev(rev), is_rev(is_rev) {
            assert(this->cap >= 0);
        }
    };

    std::vector<std::vector<Edge>> graph; // グラフの隣接リスト表現
    std::vector<int> level;          // sからの距離
    std::vector<unsigned int> iter;  // どこまで調べ終わったか

    explicit Dinic(unsigned int num_of_node) {
        assert(num_of_node > 0);
        graph.resize(num_of_node);
        level.resize(num_of_node);
        iter.resize(num_of_node);

    }

    // fromからtoへ向かう容量capの辺をグラフに追加する
    void add_edge(unsigned int from, unsigned int to, long long cap) {
        graph[from].emplace_back(Edge(to, 0, cap, (unsigned int)graph[to].size(), false));
        graph[to].emplace_back(Edge(from, cap, cap, (unsigned int)graph[from].size() - 1, true));
    }

    // sからtへの最大流を求める
    long long max_flow(unsigned int s, unsigned int t) {
        long long flow = 0;
        while (true) {
            bfs(s);
            if (level.at(t) < 0) {
                return flow;
            }
            fill(iter.begin(), iter.end(), 0);
            long long f;
            while ((f = dfs(s, t, INT_MAX)) > 0) {
                flow += f;
            }
        }
    }

private:
    // sからの最短距離をBFSで計算する
    void bfs(unsigned int s) {
        fill(level.begin(), level.end(), -1);
        std::queue<unsigned int> que;
        level.at(s) = 0;
        que.push(s);
        while (not que.empty()) {
            unsigned int v = que.front();
            que.pop();
            for (int i = 0; i < graph.at(v).size(); ++i) {
                Edge &e = graph.at(v).at(i);
                if ((e.cap - e.flow) > 0 and level.at(e.to) < 0) {
                    level.at(e.to) = level.at(v) + 1;
                    que.push(e.to);
                }
            }
        }
    }

    // 増加パスをDFSで探す
    long long dfs(unsigned int v, unsigned int t, long long f) {
        if (v == t) {
            return f;
        }
        for (unsigned int &i = iter.at(v); i < graph.at(v).size(); ++i) {
            Edge &e = graph.at(v).at(i);
            if ((e.cap - e.flow) > 0 and level.at(v) < level.at(e.to)) {
                long long d = dfs(e.to, t, std::min(f, e.cap - e.flow));
                if (d > 0) {
                    e.flow += d;
                    graph.at(e.to).at(e.rev).flow -= d;
                    return d;
                }
            }
        }
        return 0;
    }
};

using namespace std;


int main() {

    int NAB, NBA;
    cin >> NAB >> NBA;

    vector<int> C1(NAB), D1(NAB), E1(NAB);
    vector<int> C2(NBA), D2(NBA), E2(NBA);
    set<int> ta, tb;
    FOR(i, 0, NAB) {
        cin >> C1[i] >> D1[i] >> E1[i];
        ta.insert(D1[i]);
        tb.insert(E1[i]);
    }
    FOR(i, 0, NBA) {
        cin >> C2[i] >> D2[i] >> E2[i];
        tb.insert(D2[i]);
        ta.insert(E2[i]);
    }

    vector<int> time_a(ALL(ta)), time_b(ALL(tb));
    int base = time_a.size();

    map<int, int> time_index_a, time_index_b;
    FOR(i, 0, time_a.size()) {
        time_index_a[time_a.at(i)] = i;
    }
    FOR(i, 0, time_b.size()) {
        time_index_b[time_b.at(i)] = base + i;
    }

    CostScalingPushRelabel cspr(time_a.size() + time_b.size());
    Dinic dinic(time_a.size() + time_b.size());
    // A
    FOR(i, 0, time_a.size() - 1) {
        cspr.add_edge(time_index_a.at(time_a.at(i)), time_index_a.at(time_a.at(i + 1)), 10000, 0);
        dinic.add_edge(time_index_a.at(time_a.at(i)), time_index_a.at(time_a.at(i + 1)), 10000);
    }
    // B
    FOR(i, 0, time_b.size() - 1) {
        cspr.add_edge(time_index_b.at(time_b.at(i)), time_index_b.at(time_b.at(i + 1)), 10000, 0);
        dinic.add_edge(time_index_b.at(time_b.at(i)), time_index_b.at(time_b.at(i + 1)), 10000);
    }

    // A -> B
    FOR(i, 0, NAB) {
        cspr.add_edge(time_index_a.at(D1.at(i)), time_index_b.at(E1.at(i)), C1.at(i), -1);
        dinic.add_edge(time_index_a.at(D1.at(i)), time_index_b.at(E1.at(i)), C1.at(i));
    }
    // B -> A
    FOR(i, 0, NBA) {
        cspr.add_edge(time_index_b.at(D2.at(i)), time_index_a.at(E2.at(i)), C2.at(i), 0);
        dinic.add_edge(time_index_b.at(D2.at(i)), time_index_a.at(E2.at(i)), C2.at(i));
    }

    if (dinic.max_flow(time_index_a.at(time_a.at(0)), time_index_b.at(time_b.back())) == 0) {
        cout << 0 << endl;
    }
    else {
        cout << -cspr.minimum_cost_flow(time_index_a.at(time_a.at(0)), time_index_b.at(time_b.back()), 1) << endl;
    }

    return 0;
}