레이팅 미적용Interrail passes are the fun and cheap way to see more of Europe, especially if you combine your train trip with Businesslike And Penny-saving Computation! In particular, you would like to find the cheapest way to pay for your planned travels. You plan to take the train on \(n\) travel days, that are not necessarily consecutive. The individual fare is different for every day, and perhaps you can save money by buying some interrail passes.
There are \(k\) different types of interrail passes with varying costs. Each type of interrail pass can be obtained multiple times. An interrail pass is active for a period of \(p\) consecutive days, that starts on a day of your choice. The interrail pass covers the first \(d\) travel days during this period, which do not have to be consecutive. Note that an active interrail pass cannot be "paused": a day of travel counts towards the day count of each active pass, even when you pay the individual fare that day.
As an example, consider the fourth sample input, visualized in Figure . It is definitely cheaper to buy interrail passes than to pay \(4\) individual fares. The cheapest solution is to buy two interrail passes of the first type, rather than one interrail pass of the second type.
The input consists of:
- One line with two integers \(n\) and \(k\) (\(1\leq n\leq 10\,000\), \(0\leq k\leq 100\)), the number of planned travel days, and the number of types of interrail passes available.
- \(n\) lines, each with two integers \(t\) and \(f\) ($0\leq
t \leq 10^6\(, \)1\leq f\leq 10^5\(), the\ travel\ day\ and\ the\ individual\ fare\ for\ that\ day. The \)n$ travel days are distinct and given in increasing order.
- \(k\) lines, each with three integers \(p\), \(d\), and \(c\) ($1\leq
p\leq 10^6\(, \)1\leq d\leq p\(, \)1\leq c\leq 10^5\(), indicating\ a\ type\ of\ interrail\ pass\ that\ is\ valid\ for\ a\ period\ of \)p\( days, covers\ the\ first \)d\( travel\ days\ in\ that\ period, and\ costs \)c$.
Output the minimum amount you need to spend to cover all your planned travels.
2 1
0 10
1 10
2 2 15
15
2 1
0 10
2 10
2 2 15
20
3 1
0 10
1 10
2 10
5 2 15
25
4 2
3 80
5 90
24 70
26 60
5 3 100
30 5 212
200
4 1
42 9
43 2
44 9
45 9
4 3 20
29