Hemkör

Carl은 막 독립해서 이사했으며, 이제는 직접 음식을 사야 한다는 것을 깨달았다. 가게에 가는 것은 번거롭기 때문에, 대신 식료품을 문 앞까지 직접 배달해 주는 Hemkör 웹사이트에서 온라인으로 음식을 주문한다.

Carl은 이제 앞으로 다가올 수 세기 동안 먹을 음식을 사고 있다. Carl은 앞으로 $100\,000$일 동안 총 $1 \le N \le 5\,000$번의 식사(번호는 $1$부터 $N$까지)를 할 계획이다. Carl은 $i$번째 식사를 오늘로부터 $1 \le P[i] \le 100\,000$일 후에 할 생각이며, 이 식사에는 총 $1 \le Q[i] \le 100$킬로그램의 음식이 필요하다. Carl은 입맛이 까다롭지 않으므로, $Q[i]$킬로그램의 식재료만 있다면 어떤 식재료를 사용하는지는 중요하지 않다.

Hemkör에서는 서로 다른 $1 \le M \le 100\,000$개의 식료품을 판매한다. $i$번째 상품의 무게는 $1 \le V[i] \le 100$킬로그램이고, 가격은 $1 \le K[i] \le 2\,000$크로나이며, 유통기한은 오늘로부터 $1 \le D[i] \le 100\,000$일 후이다(상품은 유통기한 당일까지 사용할 수 있다). Carl은 각 식료품을 원하는 만큼 구매할 수 있다.

Carl은 모든 식사를 만들 수 있도록 식료품을 구매하는 것이 가능하다는 사실을 알아냈다. 그가 가능한 한 가장 저렴하게 식료품을 주문하도록 도와줄 수 있는가?

예제

Carl이 $1$일째와 $10$일째에 각각 무게가 $4$킬로그램과 $1$킬로그램인 $2$번의 식사를 만들 생각이라고 하자. 세 가지 식료품이 있으며, 무게는 $4$, $2$, $4$킬로그램이고, 가격은 $10$, $2$, $3$이며, 유통기한은 $10$, $5$, $5$이다. Carl은 첫 번째 상품 하나와 두 번째 상품 하나를 구매할 수 있다. 첫 번째 식사에는 각 상품을 $2$킬로그램씩 사용할 수 있다. 두 번째 식사에는 첫 번째 상품을 $1$킬로그램 사용하는데, 이 상품은 식사를 만드는 바로 그날 유통기한이 끝난다. 첫 번째 상품 중 일 킬로그램은 남아서 사용되지 않는다.

총비용은 $10 + 2 = 12$크로나이다.

채점

해결책은 여러 테스트 케이스 그룹에 대해 채점된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

1 | 31 | $N \le 100, M \le 100$

2 | 19 | 모든 식사에 대해 $P[i] = 1$

3 | 15 | 모든 상품에 대해 $V[i] = 1$

4 | 35 | 제한 없음

첫 번째 줄에는 양의 정수 $N$와 $M$가 주어진다. 이후 각 식사에 대해 한 줄씩, $N$개의 줄이 주어진다. $i$번째 줄에는 정수 $P[i]$와 $Q[i]$가 주어진다.

이후 각 상품에 대해 한 줄씩, $M$개의 줄이 주어진다. $i$번째 줄에는 정수 $V[i]$, $K[i]$, $D[i]$가 주어진다.

모든 식사에 필요한 음식을 구매하는 최소 비용을 나타내는 수 하나를 출력한다.