Một cây táo được biểu diễn bằng một đồ thị dạng cây. Đồ thị liên thông có \(N\) đỉnh và \(N - 1\) cạnh, trong đó đỉnh thứ \(i\) \((1 \le i \le N)\) có trọng số là số nguyên dương \(w_i\) biểu diễn có một quả táo ở vị trí đó với khối lượng là \(w_i\) (gram). Alice chỉ có thể mang được không quá \(S\) gram nên cô muốn chọn hái một số quả táo thỏa mãn:

1. Tổng khối lượng các quả chọn hái là không quá \(S\).
2. Hai quả được chọn hái không kề nhau.

Yêu cầu: Hãy chọn hái các quả để tổng khối lượng các quả càng lớn càng tốt.

Input

• Dòng đầu chứa hai số nguyên dương \(N, S\) \((N \le 1000; S \le 10^9)\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(w_1, w_2, \dots, w_N\) \((w_i \le 10^9)\).
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \le u, v \le N)\) mô tả các cạnh của cây.

Dữ liệu đảm bảo luôn tồn tại cách chọn để đạt được tổng bằng \(S\).

Output

• Dòng đầu ghi số nguyên \(K\) là số quả chọn hái.
• Dòng thứ hai chứa \(K\) số là chỉ số các quả chọn hái.

Example

5 10
3 7 2 8 5
1 2
2 3
3 4
4 5

3
1 3 5

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 40; S \le 10^4\) và cây có dạng đường thẳng.
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 40; S \le 10^4\).
• Subtask \(3\) (\(20\%\) số điểm): \(S \le 10^6\) và cây có dạng đường thẳng.
• Subtask \(4\) (\(30\%\) số điểm): \(S \le 10^6\).
• Subtask \(5\) (\(10\%\) số điểm): Không có ràng buộc nào thêm.

Cách chấm điểm:

Đây là bài toán chấm điểm theo tỉ lệ tối ưu. Gọi tổng khối lượng các quả táo chọn hái do thí sinh tìm được là \(P\), khi đó phần trăm số điểm đạt được cho mỗi test là \(\frac{P}{S} \cdot 100\%\).