일하기 싫어

농부 제이는 $N$칸짜리 농장을 가지고 있고, $0$일부터 $M$일까지 여러 과일을 기르려고 한다.

제이는 매일 임의의 칸에 대해 다음 일을 할 수 있다.

• 씨앗을 심는다. 해당 칸에 과일이 있으면 제거하고 새 씨앗을 심을 수 있다.
• 열매를 수확한다.

제이는 $K$가지 종류의 과일을 키울 수 있다. $i$번째 종류의 과일 정보는 다음과 같다.

• 씨앗이 자라서 첫 열매를 맺기까지 $A_i$일이 걸린다.
• 열매를 수확하면 $B_i$일 후에 다시 열매가 맺힌다.
• 한 번의 수확으로 열매 하나를 얻을 수 있고, 열매를 팔면 $C_i$만큼의 돈을 얻는다.

제이는 돈을 최대한 많이 벌고 싶어 한다.

제이는 하루에 원하는 만큼 일을 할 수 있고, 각 과일의 씨앗을 충분히 가지고 있다.

첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $(1\le N \le 1000, 1\le M \le 50, 1 \le K \le 100)$

두 번째 줄부터 $K$개의 줄에 걸쳐 $i$번째 과일의 정보 $A_i$, $B_i$, $C_i$가 공백으로 구분되어 주어진다. $(1 \le A_i, B_i \le 50, 1 \le C_i \le 1000)$

$M$일까지 농부 제이가 얻을 수 있는 돈의 최댓값을 출력한다.