Interrail Pass

Interrail passes are a fun and cheap way to see more of Europe, especially when you combine your train trip with Businesslike And Penny-saving Computation. You want to find the cheapest way to pay for your planned travels. You plan to take the train on $n$ travel days, which are not necessarily consecutive. Each day has its own individual fare. Buying some interrail passes may save money.

There are $k$ types of interrail passes with different costs. You can buy each type multiple times. A pass is active for a period of $p$ consecutive days, starting on a day you choose. The pass covers the first $d$ travel days within that period, and those days do not have to be consecutive. An active pass cannot be paused. A travel day counts toward the day count of every active pass, even if you pay the individual fare for that day.

Figure I.1 shows two pass types offered by a webshop. The first can be activated for a period of $5$ days and covers $3$ days within that period. The second has a period of $30$ days and covers $5$ days within that period. Buying passes is clearly cheaper than paying the individual fares for all $4$ travel days. The cheapest choice is two passes of the first type, which costs less than one pass of the second type.

The first line contains 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 pass types.

Each of the next $n$ lines contains 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.

Each of the next $k$ lines contains three integers $p$, $d$, and $c$ ($1\leq p\leq 10^6$, $1\leq d\leq p$, $1\leq c\leq 10^5$), describing a pass type 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.