Dush
Description
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.
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 Xi and Yi ($-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 Si, Di and Ti ($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 \le M$.
On the first line there will should one integer that represents the minimum time of the day at which everyone is showered.
Input
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 Xi and Yi ($-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 Si, Di and Ti ($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 \le M$.
Output
On the first line there will should one integer that represents the minimum time of the day at which everyone is showered.
3 5
-1 5
1 7
1 3
2 2 -1
5 5 -1
20 9 1
40 10 1
60 20 1
3 5
-1 5
1 7
1 3
2 2 -1
5 5 -1
20 10 1
40 10 1
60 20 1
43
30
Note
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.
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.