시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 1024 MB 7 5 3 100.000%

문제

Cook Bitaro is participating in a cooking contest. In this contest, a contestant is required to cook two dishes: IOI Donburi and JOI Curry.

The cooking process of IOI Donburi consists of N steps. The i-th (1 ≤ i ≤ N) step takes exactly Ai minutes. Initially, he can perform only the first step. To perform the i-th (2 ≤ i ≤ N) step, he needs to have finished the (i − 1)-th step.

The cooking process of JOI Curry consists of M steps. The j-th (1 ≤ j ≤ M) step takes exactly Bj minutes. Initially, he can perform only the first step. To perform the j-th (2 ≤ j ≤ M) step, he needs to have finished the (j − 1)-th step.

The steps need concentration, so if he starts performing a step, he cannot perform other steps until he finishes it. Between steps, he may switch from a dish to the other dish. Once the contest starts, he cannot take a rest until he completes two dishes.

By the way, in this contest, a contestant is given artistic scores as follows.

  • If he finish the i-th (1 ≤ i ≤ N) step of cooking IOI Donburi within Si minutes from the start of the contest, he is given Pi points. Here, the value of Pi might be negative.
  • If he finish the j-th (1 ≤ j ≤ M) step of cooking JOI Curry within Tj minutes from the start of the contest, he is given Qj points. Here, the value of Qj might be negative.

Bitaro wants to maximize his total artistic scores.

Write a program which, given the number of steps of cooking, the time they take, and the information of artistic scores, calculates the maximum total artistic scores Bitaro can gain

입력

Read the following data from the standard input. All the values in the input are integers.

N M
A1 S1 P1
.
.
.
AN SN PN
B1 T1 Q1
.
.
.
BM TM QM

출력

Write one line to the standard output. The output should contain the maximum total artistic scores Bitaro can gain.

제한

  • 1 ≤ N ≤ 1 000 000.
  • 1 ≤ M ≤ 1 000 000.
  • 1 ≤ Ai ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • 1 ≤ Bj ≤ 1 000 000 000 (1 ≤ j ≤ M).
  • 1 ≤ Si ≤ 2 000 000 000 000 000 = 2 × 1015 (1 ≤ i ≤ N).
  • 1 ≤ Tj ≤ 2 000 000 000 000 000 = 2 × 1015 (1 ≤ j ≤ M).
  • −1 000 000 000 ≤ Pi ≤ 1 000 000 000 (1 ≤ i ≤ N). • −1 000 000 000 ≤ Qj ≤ 1 000 000 000 (1 ≤ j ≤ M).

예제 입력 1

4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1

예제 출력 1

6

In this sample input, Bitaro can perform the steps of cooking as follows, for example:

  1. He performs the 1st step of JOI Curry. He finishes it 3 minutes after the contest starts. Since this is within 6 minutes, he gains 1 point.
  2. He performs the 1st step of IOI Donburi. He finishes it 5 minutes after the contest starts. Since this is not within 1 minute, he gains no artistic scores.
  3. He performs the 2nd step of IOI Donburi. He finishes it 8 minutes after the contest starts. Since this is within 8 minutes, he gains 1 point.
  4. He performs the 2nd step of JOI Curry. He finishes it 10 minutes after the contest starts. Since this is within 11 minutes, he gains 1 point.
  5. He performs the 3rd step of IOI Donburi. He finishes it 12 minutes after the contest starts. Since this is within 13 minutes, he gains 1 point.
  6. He performs the 4th step of IOI Donburi. He finishes it 13 minutes after the contest starts. Since this is within 13 minutes, he gains 1 point.
  7. He performs the 3rd step of JOI Curry. He finishes it 15 minutes after the contest starts. Since this is within 15 minutes, he gains 1 point.

Here the total artistic scores are 6 points. He cannot gain more than 6 points, so output 6.

예제 입력 2

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

예제 출력 2

63

예제 입력 3

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

예제 출력 3

99