32933번 - 일하기 시러

문제

농부 제이는 $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$일까지 농부 제이가 일을 했을 때 얻을 수 있는 돈의 최댓값을 출력한다.

제한

힌트