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 <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

struct MinCostFlow{
  typedef int Weight;
  struct Edge{
    int src, dst;
    Weight cap, cost;
    int rev;
    Edge(int src, int dst, Weight cap, Weight cost, int rev=-1):
      src(src), dst(dst), cap(cap), cost(cost), rev(rev) {}
  };
  typedef vector<Edge> Node;
  typedef vector<Node> Graph;
  Graph G;

  MinCostFlow(int N) : G(N) {} //頂点数Nのグラフを作る
  void add_edge(int src, int dst, Weight cap, Weight cost){
    //printf("add_edge %d -> %d : cap %d cost %d\n", src, dst, cap, cost);
    G[src].push_back(Edge(src, dst, cap, cost, G[dst].size()));
    G[dst].push_back(Edge(dst, src, 0, -cost, G[src].size() - 1));
  }
  //sからtへfを流した時の最小費用を返す O(VE + FVlogE)
  Weight flow(int s, int t, Weight f){
    //printf("%d -> %d : f = %d\n", s, t, f);
    typedef pair<Weight, int> P;
    Weight res = 0;
    int V = G.size();
    vector<int> prevv(V);
    vector<int> preve(V);
    if(s == t) return 0;
    bool start = true; 
    while(f > 0){
      vector<Weight> dist(V, INF);
      dist[s] = 0;
      REP(iter, G.size()){
        REP(v, V){
          if(dist[v] == INF) continue;
          REP(i, G[v].size()){
            Edge& e = G[v][i];
            if(e.cap > 0 && dist[e.dst] > dist[v] + e.cost){
              dist[e.dst] = dist[v] + e.cost;
              prevv[e.dst] = v;
              preve[e.dst] = i;
            }
          }
        }
      }
      if(dist[t] == INF) return -INF; //fのフローを流せないとき

      Weight d = f;
      int cycle_v = -1;
      vector<bool> used(G.size());
      for(int v = t; v != s; v = prevv[v]){
        if(used[v]) {
          cycle_v = v;
          break;
        }
        used[v] = true;
        d = min(d, G[prevv[v]][preve[v]].cap);
      }
      if(cycle_v == -1){
        f -= d;
        res += d * dist[t];
        for(int v = t; v != s; v = prevv[v]){
          Edge& e = G[prevv[v]][preve[v]];
          e.cap -= d;
          G[v][e.rev].cap += d;
        }
      }else{
        int d = INF;
        for(int v = cycle_v; ; v = prevv[v]){
          d = min(d, G[prevv[v]][preve[v]].cap);
          if(prevv[v] == cycle_v) break;
        }
        for(int v = cycle_v; ; v = prevv[v]){
          Edge& e = G[prevv[v]][preve[v]];
          e.cap -= d;
          res += d * e.cost;
          G[v][e.rev].cap += d;
          if(prevv[v] == cycle_v) break;
        }
      }
    }
    return res;
  }
};
int main(){
  int N, M;
  while(cin >> N >> M){
    vector<int> C1(N), D1(N), E1(N);
    vector<int> C2(M), D2(M), E2(M);
    REP(i, N) cin >> C1[i] >> D1[i] >> E1[i];
    REP(i, M) cin >> C2[i] >> D2[i] >> E2[i];

    vector<int> times;
    REP(i, N) times.push_back(D1[i]);
    REP(i, N) times.push_back(E1[i]);
    REP(i, M) times.push_back(D2[i]);
    REP(i, M) times.push_back(E2[i]);
    sort(times.begin(), times.end());
    times.erase(unique(times.begin(), times.end()), times.end());

    map<int, int> to_index;
    REP(i, times.size()) to_index[times[i]] = i;

    const int B = times.size();
    const int S = times.size() * 2;
    const int T = S + 1;

    MinCostFlow G(T + 1);
    REP(i, B){
      G.add_edge(S, i, 1, 0);
    }
    REP(i, B - 1){
      G.add_edge(i, i + 1, 500, 0);
      G.add_edge(B + i, B + i + 1, 500, 0);
    }
    REP(i, B){
      G.add_edge(B + i, T, 1, 0);
    }
    REP(i, N){
      int u = to_index[D1[i]];
      int v = to_index[E1[i]] + B;
      G.add_edge(u, v, C1[i], -1);
    }
    REP(i, M){
      int u = to_index[D2[i]] + B;
      int v = to_index[E2[i]];
      G.add_edge(u, v, C2[i], 0);
    }
    int ans = -G.flow(S, T, 1);
    if(ans == INF) ans = 0;
    cout << ans << endl;
  }
  return 0;
}