PivotOJ

Hemkör

시간 제한: 1000ms메모리 제한: 1024MB출처: Programmeringsolympiaden 2017 — kattBOJ 20895

문제

Carl har just flyttat hemifrån, och har insett att han numera behöver köpa mat själv. Eftersom det är jobbigt att gå till butiken beställer han istället maten online på hemsidan Hemkör, som levererar matvaror direkt till dörren.

Carl håller nu på att köpa mat för de kommande århundradena. Totalt har Carl planerat att äta 1≤N≤5 0001 \le N \le 5\,000 måltider (numrerade från 11 till NN) under de nästa 100 000100\,000 dagarna. Den ii:te måltiden tänker Carl äta 1≤P[i]≤100 0001 \le P[i] \le 100\,000 dagar från idag, och kräver totalt 1≤Q[i]≤1001 \le Q[i] \le 100 kilo mat. Carl är inte kräsen -- så länge han har Q[i]Q[i] kilo ingredienser spelar det inte någon roll vilka ingredienser han använder.

På Hemkör finns det 1≤M≤100 0001 \le M \le 100\,000 olika matvaror till salu. Den ii:te varan har en vikt 1≤V[i]≤1001 \le V[i] \le 100 kilo, en kostnad 1≤K[i]≤2 0001 \le K[i] \le 2\,000 kronor och ett utgångsdatum som är 1≤D[i]≤100 0001 \le D[i] \le 100\,000 dagar från idag (en vara kan användas fram till och med dagen den går ut). Carl kan köpa hur många exemplar av varje matvara som han vill.

Carl har kommit fram till att det går att köpa matvaror så att han kan laga samtliga måltider. Kan du hjälpa honom beställa matvaror på ett sådant sätt att det dessutom blir så billigt som möjligt?

입력

Den första raden innehåller de positiva heltalen NN och MM. Sedan följer NN rader, en för varje måltid. Den ii:te raden innehåller heltalen P[i]P[i] och Q[i]Q[i].

Sedan följer MM rader, en för varje vara. Den ii:te raden innehåller heltalen V[i]V[i], K[i]K[i] och D[i]D[i].

출력

Skriv ut ett tal -- den minimala kostnaden för att köpa mat till alla måltiderna.

예제

예제 1

입력
2 3
1 4
10 1
4 10 10
2 2 5
4 3 5
출력
12

예제 2

입력
2 3
1 2
10 1
2 10 20
1 2 5
2 3 15
출력
5
코드를 제출하려면 로그인하세요.