1 #include <cstdio>  2 #include <cstring>  3   4 namespace read  5 {  6     inline char Char(void)  7     {  8         static const int siz = 1 << 20;  9          10         static char buf[siz]; 11         static char *hd = buf + siz; 12         static char *tl = buf + siz; 13          14         if (hd == tl) 15             fread(hd = buf, 1, siz, stdin); 16          17         return *hd++; 18     } 19      20     inline int Int(void) 21     { 22         register int ret = 0, neg = 0, c = Char(); 23          24         for (; c < 48; c = Char()) 25             if (c == ‘-‘)neg ^= true; 26          27         for (; c > 47; c = Char()) 28             ret = ret * 10 + c - ‘0‘; 29          30         return neg ? -ret : ret; 31     } 32 } 33  34 const int inf = 1e9 + 7; 35  36 namespace network  37 { 38     int S, T; 39     int hd[200005]; 40     int to[1000005]; 41     int nt[1000005]; 42     int fl[1000005]; 43      44     inline void add(int u, int v, int f) 45     { 46         static int edge = 0, init = 1; 47          48         if (init)memset(hd, -1, sizeof(hd)), init = 0; 49          50         nt[edge] = hd[u]; to[edge] = v; fl[edge] = f; hd[u] = edge++; 51         nt[edge] = hd[v]; to[edge] = u; fl[edge] = 0; hd[v] = edge++; 52     } 53      54     int dep[200005]; 55      56     inline bool bfs(void) 57     { 58         static int que[200005], l, r; 59         memset(dep, 0, sizeof(dep)); 60         dep[que[l = 0] = S] = r = 1; 61          62         while (l != r) 63         { 64             int u = que[l++], v;  65              66             for (int i = hd[u]; ~i; i = nt[i]) 67                 if (fl[i] && !dep[v = to[i]]) 68                     dep[que[r++] = v] = dep[u] + 1; 69         } 70          71         return dep[T]; 72     } 73      74     inline int min(const int &a, const int &b) 75     { 76         return a < b ? a : b; 77     } 78      79     int cur[200005]; 80      81     int dfs(int u, int f) 82     { 83         if (u == T || !f) 84             return f; 85          86         int used = 0, flow, v; 87          88         for (int i = cur[u]; ~i; i = nt[i]) 89             if (fl[i] && dep[v = to[i]] == dep[u] + 1) 90             { 91                 flow = dfs(v, min(f - used, fl[i])); 92                  93                 used += flow; 94                 fl[i] -= flow; 95                 fl[i^1] += flow; 96                  97                 if (fl[i]) 98                     cur[u] = i; 99                 100                 if (f == used)101                     return f;102             }103         104         if (!used)105             dep[u] = 0;106         107         return used;108     }109     110     inline long long maxFlow(void)111     {112         long long maxFlow = 0, newFlow;113         114         while (bfs())115         {116             memcpy(cur, hd, sizeof(cur));117             118             while (newFlow = dfs(S, inf))119                 maxFlow += newFlow;120         }121         122         return maxFlow;123     }124     125     inline long long minCut(void)126     {127         return maxFlow();128     }129 }130 131 int pos[5005][2], ID;132 133 namespace segtree134 {135     struct node136     {137         int id;138         int cnt;139         node *ls;140         node *rs;141     };142     143     node *root[5005];144     145     inline node *newnode(int _cnt, node *_ls, node *_rs)146     {147         static node buf[200005], *hd = buf;148         149         hd->ls = _ls;150         hd->rs = _rs;151         hd->id = ++ID;152         hd->cnt = _cnt;153         154         return hd++;155     }156     157     node *insert(node *f, int l, int r, int pos, int fr)158     {159         node *ret;160         161         if (l == r)162             ret = newnode(f->cnt + 1, 0, 0);163         else164         {165             int mid = (l + r) >> 1;166             167             if (pos <= mid)168                 ret = newnode(f->cnt + 1, insert(f->ls, l, mid, pos, fr), f->rs);169             else170                 ret = newnode(f->cnt + 1, f->ls, insert(f->rs, mid + 1, r, pos, fr));171         }172         173         network::add(fr, ret->id, inf);174         network::add(f->id, ret->id, inf);175         176         return ret;177     }178     179     void travel(node *t, int l, int r, int x, int y, int to)180     {181         if (t->cnt == 0)return;182         183         if (l == x && r == y)184             network::add(t->id, to, inf);185         else186         {187             int mid = (l + r) >> 1;188             189             if (y <= mid)190                 travel(t->ls, l, mid, x, y, to);191             else if (x > mid)192                 travel(t->rs, mid + 1, r, x, y, to);193             else194             {195                 travel(t->ls, l, mid, x, mid, to);196                 travel(t->rs, mid + 1, r, mid + 1, y, to);197             }198         }199     }200     201     inline void init(void)202     {203         memset(root, 0, sizeof(root));204         root[0] = newnode(0, 0, 0);205         root[0]->ls = root[0];206         root[0]->rs = root[0];207     }208 }209 210 signed main(void) 211 {212     int n = read::Int();213     214     long long answer = 0;215     216     for (int i = 1; i <= n; ++i)217         pos[i][0] = ++ID,218         pos[i][1] = ++ID;219     220     segtree::init();221     222     using network::S;223     using network::T;224     225     S = 0, T = ++ID;226     227     for (int i = 1; i <= n; ++i)228     {229         using read::Int;230         using network::add;231         using segtree::root;232         using segtree::insert;233         using segtree::travel;234         235         int a = Int();236         int b = Int();237         int w = Int();238         int l = Int();239         int r = Int();240         int p = Int();241         242         answer += w;243         answer += b;244         245         add(S, pos[i][0], w);246         add(pos[i][0], T, b);247         add(pos[i][1], pos[i][0], p);248         249         static const int mx = 1000000000;250         251         root[i] = insert(root[i - 1], 0, mx, a, pos[i][0]);252         travel(root[i - 1], 0, mx, l, r, pos[i][1]);253     }254     255     printf("%lld\n", answer - network::minCut());256 }257 /* 258 Sample Input259 10260 0 1 7 3 9 2261 7 4 0 9 10 5262 1 0 4 2 10 2263 7 9 1 5 7 2264 6 3 5 3 6 2265 6 6 4 1 8 1266 6 1 6 0 6 5267 2 2 5 0 9 3268 5 1 3 0 2 5269 5 6 7 1 1 2270 271 Sample Output272 55273 */