Có ~N~ khách sạn chào giá cho thuê đến các công ty du lịch. Khách sạn thứ ~i~ cung cấp thông tin: số phòng trong khách sạn ~c_i~, chỉ số tiện nghi các phòng trong khách sạn ~f_i~ và số tiền cho thuê toàn bộ số phòng của khách sạn là ~p_i~. Các phòng trong cùng một khách sạn thì có cùng một chỉ số tiện nghi ~f~.

Các công ty du lịch khi chọn thuê một khách sạn phải chọn thuê toàn bộ số phòng khách sạn đó, không thuê lẻ từng phòng của khách sạn. Dũng đang làm nhân viên bán hàng trong công ty du lịch AlphaTour, nhận được ~M~ yêu cầu thuê phòng từ các đại lý, các yêu cầu được đánh chỉ số từ ~1~ đến ~M~. Yêu cầu thuê thứ ~i~ cũng có các thông tin: số phòng cần thuê ~C_i~, chỉ số tiện nghi tối thiểu của các phòng này ~F_i~ và giá tiền đề nghị cho yêu cầu này ~P_i~. Các phòng cung cấp cho mỗi yêu cầu không nhất thiết phải thuộc cùng một khách sạn nhưng cần đảm bảo chỉ số tiện nghi của các phòng phải lớn hơn hay bằng chỉ số tiện nghi của yêu cầu đó.

Yêu cầu: Hãy viết một chương trình giúp Dũng chọn thuê những khách sạn nào và chọn đáp ứng những yêu cầu đặt phòng nào để lợi nhuận thu được là nhiều nhất. Lợi nhuận là khoảng tiền chênh lệch giữa chi phí thuê khách sạn và số tiền thu được từ các yêu cầu được chọn.

Input

Dòng đầu là một số nguyên ~N~ ~(1 \le N \le 2000)~. Dòng thứ ~i~ trong ~N~ dòng tiếp theo cho biết thông tin chào giá của khách sạn thứ ~i~ gồm ~3~ số nguyên ~m_i, f_i, p_i~ ~(1 \le m_i \le 50, 1 \le f_i, p_i \le 10^9)~. Dòng tiếp theo chứa một số nguyên ~M~ ~(1 \le M \le 2000)~. Dòng thứ ~j~ trong ~M~ dòng tiếp theo cho biết thông tin yêu cầu thuê phòng thứ ~j~ gồm ~3~ số nguyên ~M_j, F_j, P_j~ ~(1 \le M_i \le 50, 1 \le F_i, P_i \le 10^9)~.

Output

Một số nguyên cho biết lợi nhuận tối đa khi chọn thuê khách sạn và những yêu cầu thuê phòng.

Scoring

Sample Input 1

4
5 15 50
7 20 60
6 17 55
10 18 58
3
10 19 200
10 15 140
10 10 100

Sample Output 1

82

Sample Input 2

4
5 19 50
7 20 60
6 17 55
10 18 58
3
10 19 200
10 15 140
10 10 100

Sample Output 2

172

Notes

• Test 1: Chọn thuê khách sạn số ~4~ và chọn đáp ứng yêu cầu số ~2~ để có lợi nhuận cao nhất là ~82~.
• Test 2: Chọn thuê khách sạn số ~1, 2, 4~ và chọn đáp ứng yêu cầu số ~1, 2~ để có lợi nhuận cao nhất là ~172~.