Một vương quốc cổ đại có hệ thống các hang động được nối với nhau bởi các con đường bí mật, tạo thành một cấu trúc dạng cây gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~, trong đó đỉnh ~1~ là gốc. Mỗi hang động ~u~ chứa đúng một cổ vật quý giá, với khối lượng là ~w_u~ và giá trị là ~c_u~.

Một nhà thám hiểm thực hiện ~q~ chuyến đi. Trong chuyến đi thứ ~i~, người đó di chuyển từ hang động ~u_i~ đến hang động ~v_i~ theo con đường duy nhất nối hai đỉnh này trong cây. Trong quá trình di chuyển, người thám hiểm có thể lựa chọn một số cổ vật nằm trên đường đi để mang theo. Tuy nhiên, việc lựa chọn phải thỏa mãn các điều kiện sau:

• Số lượng cổ vật được chọn không vượt quá ~k_i~;

• Tổng khối lượng của các cổ vật được chọn không vượt quá ~W~;

• Tổng giá trị của các cổ vật được chọn là lớn nhất có thể.

Yêu cầu: Với mỗi chuyến đi, hãy xác định tổng giá trị lớn nhất mà người thám hiểm có thể thu được.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n, q, W~ ~(1 \le n, q \le 2 \cdot 10^5, W \le 30)~;

• Dòng thứ hai chứa ~n~ số nguyên dương ~w_1, w_2, \dots, w_n~ (~1 \le w_i \le W~ với mọi ~1 \le i \le n~);

• Dòng thứ ba chứa ~n~ số nguyên dương ~c_1, c_2, \dots, c_n~ (~1 \le c_i \le 10^9~ với mọi ~1 \le i \le n~);

• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ cho biết có một đường đi trực tiếp giữa hai hang động ~u~ và ~v~;

• ~q~ dòng cuối, dòng thứ ~i~ chứa ba số nguyên dương ~u_i, v_i, k_i~ cho biết nhà thám hiểm trong chuyến đi thứ ~i~ xuất phát từ hang động ~u_i~, kết thúc tại hang động ~v_i~, có thể mang theo không quá ~k_i~ cổ vật ~(1 \le u_i, v_i \le n; 1 \le k_i \le 8)~ với mọi ~1 \le i \le n~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ ghi một số nguyên là kết quả của chuyến đi thứ ~i~.

Scoring

Sample Input 1

5 4 5
2 3 1 2 2
4 5 2 6 3
1 2
1 3
2 4
2 5
4 3 2
4 5 2
3 5 3
1 4 1

Sample Output 1

11
11
9
6