잠수부

잠수부는 잠수를 위해 특수 장비를 사용한다. 이 장비에는 산소를 담는 용기와 질소를 담는 용기, 두 개의 용기가 들어 있는 실린더가 달려 있다. 물속에 머무르는 시간과 잠수 깊이에 따라 필요한 산소와 질소의 양이 달라진다.

잠수부는 여러 개의 실린더를 가지고 있다. 각 실린더는 무게와, 그 안에 담긴 산소의 부피 및 질소의 부피로 나타낸다. 작업을 마치려면 고른 실린더들의 산소 총량이 필요한 산소량 이상이고 질소 총량이 필요한 질소량 이상이 되도록 실린더를 골라 가져가야 한다. 실린더는 항상 통째로 가져간다.

필요한 산소량과 질소량, 사용할 수 있는 실린더의 개수와 각 실린더의 정보가 주어질 때, 작업을 마치기 위해 가져가야 하는 실린더들의 최소 총무게를 구하는 프로그램을 작성하시오.

참고: 주어진 실린더들로는 항상 작업을 마칠 수 있다.

첫째 줄에 필요한 산소량 $t$와 질소량 $a$가 공백 하나로 구분되어 주어진다 ($1 \le t \le 21$, $1 \le a \le 79$). 단위는 리터이다.

둘째 줄에 사용할 수 있는 실린더의 개수 $n$이 주어진다 ($1 \le n \le 1000$).

이어지는 $n$개의 줄 중 $i$번째 줄에는 세 정수 $t_i$, $a_i$, $w_i$가 공백 하나로 구분되어 주어진다 ($1 \le t_i \le 21$, $1 \le a_i \le 79$, $1 \le w_i \le 800$). 각각 $i$번째 실린더의 산소 부피(리터), 질소 부피(리터), 무게(데카그램)이다.

작업을 마치기 위해 가져가야 하는 실린더들의 최소 총무게를 한 정수로 출력한다.