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~.