소 십종경기

농부 존이 기르는 소 $N$마리($1 \le N \le 20$)가 십종경기를 준비한다. 소에는 늘 그렇듯 $1$번부터 $N$번까지 번호가 붙어 있고, 종목도 $N$개다. 종목이 열 개가 아니니 $N$종 경기라고 부르는 편이 정확하겠지만, 이름은 그대로 두기로 한다.

$i$번 소가 $j$번 종목에 나가면 실력 점수 $s_{ij}$($1 \le s_{ij} \le 1000$)를 얻는다. 소 한 마리는 정확히 한 종목에만 나가고, 모든 종목에 소가 한 마리씩 배정된다.

팀의 기본 점수는 각 소가 자기가 나간 종목에서 얻은 실력 점수의 합이다. 심판은 경기가 인상적이면 여기에 보너스를 얹어 준다. 보너스는 $B$개($1 \le B \le 20$)이고, $i$번 보너스는 세 정수 $K_i$, $P_i$, $A_i$($1 \le K_i \le N$, $1 \le P_i \le 40000$, $1 \le A_i \le 1000$)로 정해진다. 앞의 $K_i$개 종목에서 팀이 $P_i$점 이상을 얻으면 $A_i$점을 더 받는다.

앞의 $K_i$개 종목에서 얻은 점수에는 그 종목들만으로 이미 받은 보너스도 들어간다. 즉 $K_j \le K_i$인 $j$번 보너스를 이미 받았다면 $A_j$도 함께 센다. 보너스는 $K$가 작은 것부터 큰 것 순서로 판정하고, $K$가 같은 보너스가 여러 개면 조건을 만족하는 보너스가 더 없을 때까지 지급을 반복한다. 한 보너스를 두 번 받지는 못한다.

예를 들어 소가 $N = 3$마리이고 실력 점수가 다음과 같다고 하자.

1번 소가 3번 종목에 나가면 팀은 7점을 얻는다. 여기에 보너스가 하나 있어서 앞의 두 종목에서 7점 이상을 얻으면 6점을 더 준다고 하자. 그러면 1번 소를 1번 종목, 2번 소를 3번 종목, 3번 소를 2번 종목에 내보내는 배정이 가장 좋다. 앞의 두 종목에서 1번 소가 5점, 3번 소가 2점을 얻어 7점이 되므로 보너스 조건을 만족한다. 총점은 $5 + 2 + 4 + 6 = 17$점이다.

총점이 가장 커지도록 소를 종목에 배정하자.

첫째 줄에 소와 종목의 수 $N$, 보너스의 수 $B$가 공백을 사이에 두고 주어진다.

다음 $B$개 줄에는 보너스 정보가 한 줄에 하나씩 주어진다. 그중 $i$번째 줄에는 $K_i$, $P_i$, $A_i$가 공백을 사이에 두고 주어진다.

다음 $N$개 줄에는 소의 실력 점수가 주어진다. 그중 $j$번째 줄에는 $j$번 소가 각 종목에서 얻는 점수 $s_{j1}, s_{j2}, \dots, s_{jN}$이 공백을 사이에 두고 주어진다.

첫째 줄에 보너스를 포함해 소들이 얻을 수 있는 최대 총점을 출력한다.