가스와 미네랄

전쟁의 흐름을 바꿀 수 있는 유물이 먼 테란 식민지 가운데 한 곳에서 발견되었다. 한편 정보부는 저그 무리가 그 식민지를 향해 이동하고 있다고 보고했다. 증원군이 도착하기 전까지 이 유물을 어떤 대가를 치르더라도 지켜야 한다.

미네랄 $m$ 단위와 베스펜 가스 $g$ 단위를 가지고 있다. 건설할 수 있는 방어 건물은 $n$ 종류다. 종류 $i$의 건물을 하나 짓는 데 미네랄 $a_i$ 단위와 가스 $b_i$ 단위가 필요하고, 기지의 방어력을 $c_i$ 단위만큼 높인다. 건물은 종류와 상관없이 몇 개든 지을 수 있으며 0개도 가능하다. 단, 모든 건물에 쓰는 미네랄 합계는 $m$을, 가스 합계는 $g$를 넘을 수 없다.

이 제약 아래에서 얻을 수 있는 방어력 합의 최댓값을 구하라.

첫 줄에 세 정수 $m$, $g$, $n$이 주어진다. 이는 각각 사용 가능한 미네랄 단위 수, 가스 단위 수, 건물 종류 수이다 ($0 \le m \le 1000$, $0 \le g \le 1000$, $1 \le n \le 10$).

이어지는 $n$개의 줄 중 $i$번째 줄에는 세 정수 $a_i$, $b_i$, $c_i$가 주어진다. 이는 종류 $i$의 건물을 짓는 데 필요한 미네랄 단위 수와 가스 단위 수, 그리고 그 방어력이다 ($1 \le a_i \le 100$, $0 \le b_i \le 100$, $0 \le c_i \le 100$).

출력

얻을 수 있는 방어력 합의 최댓값을 하나의 정수로 출력하라.