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

Đất nước VNOI là một quốc đảo tuyệt đẹp với dòng nước biển xanh biếc và các bãi cát trắng trải dài vô tận. Đất nước bao gồm ~n~ hòn đảo được kết nối với nhau bởi ~n-1~ cây cầu đảm bảo luôn có đường đi giữa hai hòn đảo bất kì. Nhân mùa du lịch năm ~2023~ chuẩn bị đến, chính phủ VNOI ban hành một chính sách đặc biệt nhằm thu hút khách du lịch: Mỗi du khách khi đến thăm hòn đảo thứ ~i~ sẽ nhận được một phần quà đặc biệt là một kí tự ~c_i~.

Ngay sau khi chính sách được ban hành, đã có hàng loạt du khách đặt vé du lịch đến đất nước VNOI. Chính phủ VNOI tính toán được rằng, sẽ có ~Q~ vị khách du lịch ghé thăm đất nước. Vị khách thứ ~i~ sẽ bắt đầu chuyến thăm quan của mình tại hòn đảo ~u_i~ và anh ta muốn thu thập được các món quà lần lượt được thể hiện qua xâu ~s_i~. Hành trình của vị khách sẽ bắt đầu tại hòn đảo ~u_i~ và đi qua một số hòn đảo sao cho không có hòn đảo nào được đi qua ~2~ lần. Tuy nhiên, do hiện nay đang diễn ra đại chiến ICPC tại hòn đảo thứ ~1~ nên các du khách sẽ muốn hạn chế lại gần hòn đảo này. Vì thế hành trình du lịch của vị khách thứ ~i~ sẽ không được phép đi qua các hòn đảo có khoảng cách đến hòn đảo thứ ~1~ nhỏ hơn khoảng cách từ hòn đảo ~u_i~ đến hòn đảo thứ ~1~.

Yêu cầu: Với mỗi vị khách du lịch hãy giúp chính phủ VNOI tính toán số lượng hành trình du lịch thỏa mãn mong muốn của vị khách ấy nhé!

Input

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

• Dòng đầu tiên chứa số ~n~ và ~Q~ cho biết số hòn đảo và số lượng du khách đến thăm đất nước VNOI ~(1 \leq n,Q \leq 2 \cdot 10^5)~.

• Dòng thứ hai chứa ~n~ kí tự ~c_i~ (~c_i~ là một kí tự tiếng Anh in thường) thể hiện các phần quà nhận được khi đến hòn đảo ~i~.

• ~n - 1~ dòng tiếp theo mỗi dòng chứa 2 số ~u~ ~v~ thể hiện có cây cầu kết nối giữa hòn đảo ~u~ và hòn đảo ~v~ ~(1 \leq u,v \leq n)~.

• ~Q~ dòng cuối, dòng thứ ~i~ chứa hòn đảo bắt đầu ~u_i~ và xâu thể hiện dãy các món quà mà vị khách thứ ~i~ muốn thu thập.

Dữ liệu đảm bảo tổng độ dài các xâu ~s_i \leq 5 \cdot 10^5~.

Output

Đưa ra file văn bản str.out ~Q~ dòng:

• Dòng thứ ~i~ thể hiện số lượng hành trình thỏa mãn yêu cầu của vị khách thứ ~i~.

Scoring

Gọi S là tổng độ dài các xâu ~s_i~.

Sample Input 1

10 10
iotmmoomoo
6 8
5 7
9 4
2 4
4 7
10 3
7 1
8 10
8 7
7 omo
7 omo
1 iomo
7 omo
1 iomo
1 iomo
1 iomo
1 iomo
1 iomo
7 omo

Sample Output 1

4
4
4
4
4
4
4
4
4
4

Trung đi ăn nhà hàng, trên menu có bán ~n~ món đồ. Trung biết rằng món đồ thứ ~i~ có độ no là ~a_i~, độ ngon là ~b_i~ và giá tiền là ~c_i~.

Trung đang muốn gọi món; tuy nhiên, vì Trung đến quá sát giờ đóng cửa, nên với mỗi một món Trung chỉ có thể gọi món đó tối đa ~1~ lần. Ngoài ra, để ăn cho đúng kiểu, Trung đã đề ra ~m~ chỉ tiêu, với chỉ tiêu thứ ~i~ có dạng (~u_i~,~v_i~) nghĩa là nếu Trung gọi món thứ ~u_i~ thì Trung phải gọi món thứ ~v_i~.

Trung muốn sau khi ăn xong thì độ hạnh phúc đạt được là tối đa. Giả sử như Trung gọi một tập các món đồ ~S~, thì độ hạnh phúc của Trung được định nghĩa là tích của tổng độ no và tổng độ ngon, trừ đi số tiền mà Trung phải trả. Nói cách khác, độ hạnh phúc của Trung là ~(\sum_{i \in S} a_i)(\sum_{i \in S} b_i) - (\sum_{i \in S} c_i)~.

Yêu cầu: Hãy tìm độ hạnh phúc tối đa mà Trung có thể đạt được.

Input

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

• Dòng đầu chứa hai số nguyên ~n~ và ~m~ (~n \le 200~, ~m \le n^2~) — số món đồ và số chỉ tiêu.

• ~n~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a_i, b_i, c_i~ (~1 \le a_i, b_i, c_i \le 10^6~) — độ no, độ ngon, giá tiền của món thứ ~i~.

• ~m~ dòng cuối, mỗi dòng chứa hai số nguyên ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~) — chỉ tiêu thứ ~i~.

Output

Đưa ra file văn bản restaurant.out một số nguyên duy nhất là độ hạnh phúc tối đa mà Trung có thể đạt được.

Scoring

Sample Input 1

5 2
2 12 218
1 1 7
6 1 19
6 2 127
5 4 9
1 2
2 3

Sample Output 1

37

Notes

Ở ví dụ trên, cách tối ưu là Trung gọi món ~2~, ~3~ và ~5~. Khi đó độ hạnh phúc của Trung là (~1 + 6 + 5~) ~*~ (~1 + 1 + 4~) ~-~ (~7 + 19 + 9~) ~=~ ~37~.