RCPC Simulare 2023 day 2 | L. Dush

Sannu went on a trip to the mountains together with his friend group. Altogether there were $N$ 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 $N$ and $M$ ($1 \leq N \leq 20$ and $1 \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 $N$ lines contain two integers $X_i$ and $Y_i$ ($-1 \leq X_i \leq 1$ and $1 \leq Y_i \leq 10^9$) -- the type of water preferred by the $i$-th person, as well as the time needed for the $i^{th}$ person's shower.

The next $M$ lines each contain three numbers $S_i$, $D_i$ and $T_i$ ($1 \leq S_i, D_i \leq 10^9$, $-1 \leq T_i \leq 1$) -- starting time, the time duration in which there is water and the water type of the $i^{th}$ timeslot with water. Furthermore, these timeslots are not overlapping ($S_i + D_i\leq S_{i+1}$) for all $1 \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.