Phi thuyền ABCXYZ đang trong một cuộc hành trình thám hiểm không gian trong D ngày.

Mỗi ngày phi thuyền cần phải tiếp nhiên liệu một lần. Nơi tiếp nhiên liệu là các hành tinh, ở thiên hà 123456, có t loại hành tinh khác nhau được đánh số từ 0 tới t-1. Ở ngày thứ i của cuộc hành trình, phi thuyền ABCXYZ chỉ có thể tiếp nhiên liệu ở hành tinh loại mission[i].

Có n tiểu hành tinh trong thiên hà 123456, mỗi hành tinh được biểu diễn bởi cặp tọa độ (x,y) và loại hành tinh của nó trong t loại hành tinh. Tìm độ dài đường đi tiếp nhiên liệu của phi thuyền ABCXYZ sao cho độ dài này là ngắn nhất để tiết kiệm thời gian và nhiên liệu.

Khoảng cách giữa hai hành tinh được tính theo khoảng cách Manhattan. (Ex : có hai cặp tọa độ (1,5) (9,3). Khoảng cách Manhattan của cặp tọa độ này là : |1-9|+|5-3| = 10).

Lưu ý có thể tiếp nhiên liệu ở một hành tinh e trong n hành tinh nhiều hơn một lần.

Input :

Dòng đầu : số loại hành tinh t trong thiên hà 123456 (1 <= t <= 500)

Dòng hai : n : số hành tinh trong thiên hà 123456 (0 <= n <= 500)

n dòng tiếp theo, môi dòng gồm bộ 3 số (x,y,l) trong đó, x,y là tọa độ của hành tinh, l là loại của hành tinh đó. (0 <= x <= 1000000, 0 <= y <= 1000000, 0<=k < t)

Dòng tiếp theo, số ngày D của cuộc hành trình (1 <= D <= 500)

Dòng cuối gồm D số, loại hành tinh mission[i] nơi phi thuyền phải tiếp nhiên liệu cho mỗi ngày trong cuộc hành trình. (1 <= D <= 500, 0 <= mission[i] <= 500)