Under construction

Still being built. Things may change

Two Dishes

Time limit5sMemory limit1024 MB

Summary
Interleave two chains of timed steps so that each step finishing before its deadline adds its score, and find the maximum total score.
Level

Hard9 of 10

Topics
Dynamic programming, Graph, Shortest path
Solved
No attempts yet

Problem

Chef Vitaro is taking part in a cooking contest. Contestants must cook IOI Donburi and JOI Curry.

IOI Donburi has NN steps. Step ii (1≤i≤N1 \le i \le N) takes exactly AiA_i minutes. At first, he can only run step 1. To run step ii (2≤i≤N2 \le i \le N), he must have finished step i−1i-1.

JOI Curry has MM steps. Step jj (1≤j≤M1 \le j \le M) takes exactly BjB_j minutes. At first, he can only run step 1. To run step jj (2≤j≤M2 \le j \le M), he must have finished step j−1j-1.

He must concentrate on each step. Once a step starts, no other step can run until it ends. After a step ends, he may start a step of the other dish. There are no breaks from the start of the contest until both dishes are finished.

In this contest, each contestant receives an art score by these rules.

  • If he finishes step ii of IOI Donburi (1≤i≤N1 \le i \le N) within SiS_i minutes from the start, he gets PiP_i points. PiP_i may be negative.
  • If he finishes step jj of JOI Curry (1≤j≤M1 \le j \le M) within TjT_j minutes from the start, he gets QjQ_j points. QjQ_j may be negative.

Vitaro wants to maximize his art score. Given the number of steps, the time each step takes, and the art score information, find the maximum art score Vitaro can get.

Input

The first line contains NN and MM.

Each of the next NN lines contains AiA_i, SiS_i, and PiP_i.

Each of the following MM lines contains BjB_j, TjT_j, and QjQ_j.

All values are integers.

Output

Print one line containing the maximum art score Vitaro can get.

Constraints

  • 1≤N≤1 000 0001 \le N \le 1\,000\,000.
  • 1≤M≤1 000 0001 \le M \le 1\,000\,000.
  • 1≤Ai≤1 000 000 0001 \le A_i \le 1\,000\,000\,000 (1≤i≤N1 \le i \le N).
  • 1≤Bj≤1 000 000 0001 \le B_j \le 1\,000\,000\,000 (1≤j≤M1 \le j \le M).
  • 1≤Si≤2×10151 \le S_i \le 2 \times 10^{15} (1≤i≤N1 \le i \le N).
  • 1≤Tj≤2×10151 \le T_j \le 2 \times 10^{15} (1≤j≤M1 \le j \le M).
  • −1 000 000 000≤Pi≤1 000 000 000-1\,000\,000\,000 \le P_i \le 1\,000\,000\,000 (1≤i≤N1 \le i \le N).
  • −1 000 000 000≤Qj≤1 000 000 000-1\,000\,000\,000 \le Q_j \le 1\,000\,000\,000 (1≤j≤M1 \le j \le M).

Examples3

  1. Example 1

    Input
    4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1
    Expected output
    6

  2. Example 2

    Input
    5 7
16 73 16
17 73 10
20 73 1
14 73 16
18 73 10
3 73 2
10 73 7
16 73 19
12 73 4
15 73 15
20 73 14
15 73 8
    Expected output
    63

  3. Example 3

    Input
    9 11
86 565 58
41 469 -95
73 679 28
91 585 -78
17 513 -63
48 878 -66
66 901 59
72 983 -70
68 1432 11
42 386 -87
36 895 57
100 164 10
96 812 -6
23 961 -66
54 193 51
37 709 82
62 148 -36
28 853 22
15 44 53
77 660 -19
    Expected output
    99