Płetwonurek do nurkowania używa butli, w której są dwa zbiorniki: z tlenem i azotem. W zależności od czasu przebywania pod wodą i głębokości nurek potrzebuje różnych ilości tlenu i azotu. Płetwonurek ma do dyspozycji pewną liczbę butli. Każda butla charakteryzuje się wagą oraz objętością zawartego w niej tlenu i azotu. Do wykonania zadania nurek potrzebuje określonych ilości tlenu i azotu. Jaka jest najmniejsza sumaryczna waga butli, które nurek musi zabrać ze sobą, żeby mógł wykonać zadanie?

Zadanie
Napisz program, który oblicza najmniejszą sumaryczną wagę butli, które nurek musi zabrać ze sobą, żeby wykonać zadanie.

Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita, oznaczająca liczbę zestawów danych, które za chwilę pojawią się na wejściu. W pierwszym wierszu zestawu znajdują się dwie liczby całkowite t i a oddzielone pojedynczym odstępem (1<=t<=21, 1<=a<=79) Są to odpowiednio, ilość tlenu i ilość azotu potrzebne do wykonania zadania. Drugi wiersz zawiera tylko jedną liczbę n (1<=n<=1000), która oznacza liczbę dostępnych butli. Kolejne n wierszy zawiera charakterystyki butli. Wiersz i+2 zawiera trzy liczby całkowite ti, ai, wi, pooddzielane pojedynczymi odstępami (1<=ti<=21, 1<=ai<=79, 1<=wi<=800). Są to kolejno: objętości tlenu i azotu w i-tej butli oraz waga tej butli.

Wyjście
Program powinien wypisać jedną liczbę całkowitą, która powinna być najmniejszą sumaryczną wagą butli, które nurek musi zabrać ze sobą, żeby mógł wykonać zadanie.

Przykład

wejście:
1
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

wyjście:
249