• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۶۴ مگابایت

در بازی OSTADD که یک بازی جنگی است $n$ نوع تفنگ وجود دارد که تفنگ $i$ام $t_i$ تیر دارد که هر تیر $p_i$ قدرت دارد و برای خریدش $c_i$ هزینه لازم است. دشمن $m$ گروه دارد که گروه $i$ام $a_i$ نفر هستند و هر کدام $b_i$ جان دارد (یعنی برای این که بمیرد باید تیری به قدرت بیشتر مساوی $b_i$ به او شلیک کرد). ما می‌خواهیم همه افراد دشمن را با زدن دقيقاً یک تیر به هر یک از آن‌ها بکشیم. حداقل هزینه برای خرید تفنگ برای کشتن تمام افراد دشمن چه قدر است.

ورودی

در سطر اول عدد $n$ می‌آید و در $n$ سطر بعدی در هر سطر به ترتیب $t_i$، $p_i$ و $c_i$ که اطلاعات تفنگ $i$ام است می‌آید و در سطر بعد عدد $m$ و در $m$ سطر بعدی در هر سطر به تریب $a_i$ و $b_i$ می‌آید که اطلاعات گروه $i$ام دشمن است. $$1 \leq n, m \leq 500$$ $$1 \leq a_i, t_i \leq 100$$ $$1 \leq p_i, b_i, c_i \leq 1000000000$$

خروجی

حداقل هزینه برای خرید تفنگ برای کشتن تمام افراد دشمن چه قدر است. اگر این کار ممکن نیست -1 چاپ کنید.

مثال‌ها

ورودی نمونه ۱

2
2 3 5
1 4 10
1
3 2

خروجی نمونه ۱

15

ورودی نمونه ۲

3
2 3 5
2 4 10
4 4 20
2
1 4
3 3

خروجی نمونه ۲

15

ورودی نمونه ۳

1
5 3 10
1
3 5

خروجی نمونه ۳

-1