L. Dush

Time limit: 2s Memory limit: 256MB Input: Output:

Sannu went on a trip to the mountains together with his friend group. Altogether there were NN people gathered in a cabin in order to watch all of One Piece, and they decided to go eat at a nearby restaurant on the third day of their trip. Although their rented cabin had enough bathrooms, only one shower was usable. From Sannu's keen observations during the second day, they discovered that that shower has running water just at some moments during the day, and you cannot control the temperature of the water. Sometimes there is hot water, sometimes lukewarm, sometimes only cold water and during the rest of the day there is no water running from the shower. Knowing the preferred water temperature for each person, as well as how much each person stays in the shower, please find out what is the earliest moment of the day in which everyone has showered (and is ready to leave for the restaurant). Do note that, due to the size of the shower cabin, only one person can take a shower at a given time, and since anyone would be annoyed if they had to interrupt their shower, each person must get into the shower exactly once (in only one showering timeslot).

Input data

The first line of the input contains two integers NN and MM (1N201 \leq N \leq 20 and 1M1051 \leq M \leq 10^5) -- the number of people at the cabin and the number of timeslots where there is water running in the shower.

The next NN lines contain two integers XiX_i and YiY_i (1Xi1-1 \leq X_i \leq 1 and 1Yi1091 \leq Y_i \leq 10^9) -- the type of water preferred by the ii-th person, as well as the time needed for the ithi^{th} person's shower.

The next MM lines each contain three numbers SiS_i, DiD_i and TiT_i (1Si,Di1091 \leq S_i, D_i \leq 10^9, 1Ti1-1 \leq T_i \leq 1) -- starting time, the time duration in which there is water and the water type of the ithi^{th} timeslot with water. Furthermore, these timeslots are not overlapping (Si+DiSi+1S_i + D_i\leq S_{i+1}) for all 1iM1 \leq i \leq M.

Output data

On the first line there will should one integer that represents the minimum time of the day at which everyone is showered.

Example 1

stdin

3 5
-1 5
1 7
1 3
2 2 -1
5 5 -1
20 9 1
40 10 1
60 20 1

stdout

43

Explanation

In the first case, the first person will take a shower in the second timeslot, the second person in the third timeslot, and the third one in the fourth timeslot, finishing his shower at time 43.

Example 2

stdin

3 5
-1 5
1 7
1 3
2 2 -1
5 5 -1
20 10 1
40 10 1
60 20 1

stdout

30

Explanation

In the second case, the first person will take a shower in the second timeslot, the second person in the third timeslot, and the third one in the third timeslot after the second one, finishing his shower at time 30.

Log in or sign up to be able to send submissions!