1 /**************************************************************  2     Problem: 3218  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:3084 ms  7     Memory:29732 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13   14 #define p1(i) i * 2 - 1 15 #define p2(i) i * 2 16 using namespace std; 17 typedef long long ll; 18 const int N = 5005; 19 const int N1 = 200005; 20 const int M = N1 * 10; 21 const int inf = 1e9; 22   23 struct edge { 24   int next, to, f; 25   edge() {} 26   edge(int _n, int _t, int _f) : next(_n), to(_t), f(_f) {} 27 } e[M]; 28   29 struct seg_node { 30   seg_node *ls, *rs; 31   int cnt, w; 32 } *seg[N], mempool[N1], *cnt_seg = mempool; 33   34 int n, cnt_p, S, T; 35 int first[N1], tot = 1; 36 int d[N1], q[N1]; 37 ll ans; 38   39 int read() { 40   int x = 0; 41   char ch = getchar(); 42   while (ch < ‘0‘ || ‘9‘ < ch) 43     ch = getchar(); 44   while (‘0‘ <= ch && ch <= ‘9‘) 45     (x *= 10) += ch - ‘0‘, ch = getchar(); 46   return x; 47 } 48   49 inline void add_edges(int x, int y, int z) { 50   e[++tot] = edge(first[x], y, z), first[x] = tot; 51   e[++tot] = edge(first[y], x, 0), first[y] = tot; 52 } 53   54 #define y e[x].to 55 #define p q[l] 56 bool bfs() { 57   int l, r, x; 58   memset(d, -1, sizeof(d)); 59   d[q[1] = S] = 1; 60   for (l = r = 1; l != r + 1; ++l) 61     for (x = first[p]; x; x = e[x].next) 62       if (!~d[y] && e[x].f) { 63     d[q[++r] = y] = d[p] + 1; 64     if (y == T) return 1; 65       } 66   return 0; 67 } 68 #undef p 69   70 int dfs(int p, int lim) { 71   if (p == T || !lim) return lim; 72   int x, tmp, rest = lim; 73   for (x = first[p]; x && rest; x = e[x].next)  74     if (d[y] == d[p] + 1 && ((tmp = min(e[x].f, rest)) > 0)) { 75       rest -= (tmp = dfs(y, tmp)); 76       e[x].f -= tmp, e[x ^ 1].f += tmp; 77       if (!rest) return lim; 78     } 79   if (rest) d[p] = -1; 80   return lim - rest; 81 } 82 #undef y 83   84 ll Dinic() { 85   ll res = 0; 86   while (bfs()) 87     res += dfs(S, inf); 88   return res; 89 } 90   91   92 #define mid (l + r >> 1) 93 void seg_insert(seg_node *&p, int l, int r, int pos, int from) { 94   add_edges(from, cnt_p + 1, inf), add_edges(p -> w, cnt_p + 1, inf); 95   *(++cnt_seg) = *p, p = cnt_seg; 96   ++(p -> cnt), p -> w = ++cnt_p; 97   if (l == r) return; 98   if (pos <= mid) seg_insert(p -> ls, l, mid, pos, from); 99   else seg_insert(p -> rs, mid + 1, r, pos, from);100 }101  102 void seg_work(seg_node *p, int l, int r, int L, int R, int to) {103   if (!(p -> cnt)) return;104   if (l == L && R == r) {105     add_edges(p -> w, to, inf);106     return;107   }108   if (R <= mid) seg_work(p -> ls, l, mid, L, R, to);109   else if (mid < L) seg_work(p -> rs, mid + 1, r, L, R, to);110   else seg_work(p -> ls, l, mid, L, mid, to), seg_work(p -> rs, mid + 1, r, mid + 1, R, to);111 }112 #undef mid113  114 int main() {115   int i, a, b, w, l, r, p;116   n = read(), S = n << 1 | 1, T = cnt_p = S + 1;117   seg[0] = ++cnt_seg;118   seg[0] -> ls = seg[0] -> rs = seg[0];119   for (i = 1; i <= n; ++i) {120     a = read(), b = read(), w = read(), l = read(), r = read(), p = read();121     add_edges(S, p1(i), w), add_edges(p1(i), T, b);122     seg_insert(seg[i] = seg[i - 1], 0, inf, a, p1(i));123     seg_work(seg[i - 1], 0, inf, l, r, p2(i));124     add_edges(p2(i), p1(i), p);125     ans += w + b;126   }127   printf("%lld\n", ans - Dinic());128   return 0;129 }