B. Ремонт
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

После покупки собственной квартиры Боря решил поклеить в каждой комнате обои. В Бориной квартире n комнат, каждая из которых имеет форму прямоугольного параллелепипеда. Про каждую комнату известны длина, ширина и высота стен в метрах (разные комнаты могут иметь разные размеры, в том числе и высоту).

Боря выбрал m типов обоев, которыми он хочет обклеить стены комнат (но не обязательно использовать все типы). Каждый тип обоев продается в рулонах фиксированной длины и ширины (длина, естественно, в размотанном состоянии). Кроме того, для каждого типа известна стоимость одного рулона этого типа.

На обоях каждого типа изображены полоски, идущие вдоль длины рулона. При поклейке полоски обязательно должны располагаться строго вертикально (поэтому рулон нельзя поворачивать, даже если длина меньше ширины). При этом рулоны можно резать произвольным образом, но стыки наклеенных кусков также должны быть вертикальными. Кроме того, в каждой комнате должны использоваться обои только одного типа, и куски одного и того же рулона нельзя клеить в разных комнатах, то есть для каждой комнаты рулоны закупаются отдельно. При этом некоторые рулоны могут быть использованы не полностью.

После покупки квартиры у Бори туго со средствами, поэтому он хочет потратить на обои минимальную сумму. Помогите ему.

Входные данные

В первой строке находится натуральное число n (1 ≤ n ≤ 500) — количество комнат в Бориной квартире.

В каждой из следующих n строк находится по три натуральных числа, разделенных пробелами — длина, ширина и высота стен в метрах очередной комнаты соответственно.

В следующей строке находится натуральное число m (1 ≤ m ≤ 500) — количество доступных типов обоев.

В каждой из следующих m строк находится по три натуральных числа, разделенных пробелами — длина и ширина в метрах, а также стоимость одного рулона очередного типа обоев соответственно.

Все числа во входных данных не превосходят 500. Гарантируется, что каждую комнату можно обклеить, используя данные типы обоев.

Выходные данные

Выведите одно число — минимальную суммарную стоимость рулонов.

Примеры
Входные данные
1
5 5 3
3
10 1 100
15 2 320
3 19 500
Выходные данные
640
Примечание

Комментарий к примеру:

Суммарная длина стен (периметр) комнаты — 20 м.

Из одного рулона первого типа можно сделать три вертикальные полоски шириной 1 м., значит, нужно 7 рулонов этого типа, цена — 700.

Из рулона второго типа получается пять полосок ширины 2 м., нужно 2 рулона, цена — 640.

Одним рулоном третьего типа получится сразу заклеить 19 м. из 20, но пользоваться другими типами уже нельзя и придется докупать второй, цена — 1000.