인터레일 패스

인터레일 패스는 유럽을 더 많이, 그리고 싸게 둘러보는 방법이다. 특히 기차 여행을 Businesslike And Penny-saving Computation과 함께 하면 더 좋다. 계획한 여행의 비용을 가장 싸게 치르는 방법을 찾고 싶다. 연속일 수도 있고 아닐 수도 있는 $n$일 동안 기차를 탈 계획이다. 날마다 개별 운임이 다르다. 패스를 몇 장 사면 돈을 아낄 수 있다.

비용이 서로 다른 인터레일 패스가 $k$종류 있다. 각 종류는 여러 번 살 수 있다. 패스는 여러분이 고른 날부터 시작하는 $p$일 연속 기간 동안 유효하다. 패스는 그 기간 안의 처음 $d$번의 여행일을 덮는다. 이 여행일들은 연속일 필요가 없다. 유효한 패스는 멈출 수 없다. 여행일은 그날 개별 운임을 내더라도 유효한 모든 패스의 날짜 수에 포함된다.

그림 I.1은 웹 상점이 파는 두 종류의 패스를 보여 준다. 첫 번째 패스는 $5$일 동안 활성화할 수 있고 그 안의 $3$일을 덮는다. 두 번째 패스는 기간이 $30$일이고 그 안의 $5$일을 덮는다. 여행일 $4$일 모두에 개별 운임을 내는 것보다 패스를 사는 편이 확실히 싸다. 가장 싼 선택은 첫 번째 종류 패스를 두 장 사는 것이다. 두 번째 종류 패스 한 장보다 저렴하다.

첫 줄에 두 정수 $n$과 $k$가 주어진다 ($1\leq n\leq 10\,000$, $0\leq k\leq 100$). 계획한 여행일의 수와 패스 종류의 수이다.

다음 $n$개의 줄에는 각각 두 정수 $t$와 $f$가 주어진다 ($0\leq t \leq 10^6$, $1\leq f\leq 10^5$). $t$는 여행일이고 $f$는 그날의 개별 운임이다. $n$개의 여행일은 서로 다르며 증가하는 순서로 주어진다.

다음 $k$개의 줄에는 각각 세 정수 $p$, $d$, $c$가 주어진다 ($1\leq p\leq 10^6$, $1\leq d\leq p$, $1\leq c\leq 10^5$). 유효 기간이 $p$일이고, 그 기간 안의 처음 $d$번의 여행일을 덮으며, 가격이 $c$인 패스 종류를 뜻한다.

계획한 모든 여행을 덮는 데 드는 최소 금액을 출력한다.