Trung rất thích câu cá. Hôm nay cậu đi câu cá ở điểm câu bên hồ có ~n~ con cá, con cá thứ ~i~ có cân nặng ~w_i~, cách vị trí câu ~d_i~ mét, và khi bán con cá này, ta thu được một khoảng tiền là ~a_i~.

Tiệm đồ câu có ~m~ loại cần câu, loại cần thứ ~i~ chịu được cân nặng tối đa ~x_i~ và có giá ~c_i~. Dây cước có giá ~b~ đồng cho mỗi mét dây cước. Để câu được con cá thứ ~i~, cần câu Trung mua phải chịu được cân nặng của con cá (~x \geq w_i~) và độ dài dây cước không được nhỏ hơn khoảng cách của con cá thứ ~i~ tới điểm câu. Một cần câu có thể được sử dụng lại nhiều lần.

Yêu cầu: Tính số tiền lời tối đa của Trung sau chuyến đi câu.

Input

Vào từ file văn bản fishing.inp:

• Dòng đầu chứa một số nguyên dương ~n~, số lượng cá trong hồ ~(1 \leq n \leq 2\cdot10^5)~.

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương ~w_i, d_i, a_i~, lần lượt là cân nặng, khoảng cách tới vị trí câu và giá trị của con cá thứ ~i~ ~(1 \leq w_i, d_i, a_i \leq 10^9)~.

• Dòng tiếp theo gồm số nguyên dương ~m~, số lượng cần câu ở tiệm đồ ~(1 \leq m \leq 2\cdot10^5)~.

• Dòng thứ ~i~ trong ~m~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương ~x_i, c_i~, lần lượt là cân nặng tối đa cần chịu được và giá của cần câu thứ ~i~ ~(1 \leq x_i, c_i \leq 10^9)~.

• Dòng cuối chứa số nguyên ~b~, giá tiền của mỗi mét dây câu ~(1 \leq b \leq 10^9)~.

Output

Đưa ra file văn bản fishing.out một số nguyên duy nhất là lợi nhận tối đa của Trung sau chuyến đi câu.

Scoring

Sample Input 1

3
4 3 10
2 5 4
1 2 1
3
6 100
2 7
4 3
1

Sample Output 1

7