Hãng hàng không DelayAir có ~n~ sân bay đánh số từ ~1~ đến ~n~. Biết rằng:

• Thời gian bay từ sân bay ~i~ sang sân bay ~j~ mất ~t_{ij}~ đơn vị thời gian. Chú ý ~t_{ij}~ có thể khác ~t_{ji}~.
• Khi máy bay hạ cánh xuống sân bay ~i~ (~1 \le i \le n~) thì phải trải qua quá trình bảo trì (như dọn vệ sinh, tiếp nhiên liệu...) nên phải sau ~p_i~ đơn vị thời gian mới có thể cất cánh tiếp.

Hãng nhận được ~m~ đơn đặt hàng của công ty HHH, mỗi đơn đặt hàng cho biết sân bay cất cánh, sân bay hạ cánh và thời gian cất cánh. Bạn hãy giúp ban điều hành bay xem phải có tối thiểu bao nhiêu máy bay để thỏa mãn được ~m~ đơn đặt hàng.

Yêu cầu: Xác định số máy bay tối thiểu cần sử dụng để đáp ứng tất cả các đơn đặt hàng.

Input

• Dòng đầu chứa 2 số nguyên dương ~n~ và ~m~ (~1 \le n \le 500, 1 \le m \le 500~).
• Dòng tiếp theo chứa ~n~ số nguyên ~p_1, p_2, \dots, p_n~ là thời gian bảo trì máy bay ở mỗi sân bay (~0 \le p_i \le 10^6~).
• ~n~ dòng tiếp theo, dòng thứ ~i~ ghi ~n~ số nguyên dương, số thứ ~j~ là ~t_{ij}~, trong trường hợp ~i = j~ thì ~t_{ij} = 0~ (~1 \le t_{ij} \le 10^6~).
• ~m~ dòng tiếp theo mỗi dòng ghi một yêu cầu bay gồm 3 số ~a, b, c~ tương ứng là cất cánh từ sân bay ~a~ vào thời điểm ~c~, hạ cánh tại sân bay ~b~ (~1 \le c \le 10^6~).

Output

• Ghi ra một số nguyên duy nhất là số máy bay tối thiểu phải sử dụng.

Sample Input 1

2 2
2 2
0 1
1 0
1 2 1
2 1 1

Sample Output 1

2

Sample Input 2

2 2
2 2
0 1
1 0
1 2 1
2 1 3

Sample Output 2

1