Ban tổ chức Olympic 30/4 thiết kế một cuộc thi lập trình điều khiển robot cho các thí sinh yêu thích tin học. Họ tạo ra một sơ đồ gồm \(n\) địa điểm được đánh số từ \(1\) đến \(n\) và được nối với nhau bởi \(m\) con đường hai chiều.

Mỗi con đường thứ \(i\) nối hai địa điểm \(u_i\) và \(v_i\) với một trọng số nhất định. Khi robot di chuyển đến một địa điểm mới, nó nhận được một số điểm thưởng. Tuy nhiên, nếu robot đi qua một con đường có trọng số lớn hơn điểm thưởng hiện tại, nó sẽ bị phạt một thẻ. Robot chỉ được phép nhận tối đa \(k\) thẻ phạt. Khi đã nhận đủ \(k\) thẻ phạt, robot sẽ không thể nhận thêm điểm thưởng ở bất kỳ địa điểm nào nữa.

Yêu cầu

• Xác định số lượng địa điểm lớn nhất mà robot có thể đi qua.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên \(n, m, s, k\) (với \(n\) tối đa \(100000\), \(m\) tối đa \(200000\), \(s\) là địa điểm xuất phát và \(k\) có giá trị không quá \(1\)).
• Dòng thứ hai chứa \(n\) số nguyên là số điểm thưởng mà robot nhận được khi đến mỗi địa điểm.
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u_i, v_i, w_i\) (cho biết có con đường nối trực tiếp giữa hai địa điểm với trọng số tương ứng).

Dữ liệu ra

• Một số nguyên duy nhất là số địa điểm lớn nhất mà robot có thể đi qua.

Input 1

6 7 3 1
3 4 2 3 2 7
1 6 10
1 5 8
5 2 12
2 6 10
2 3 5
3 4 1
3 5 11

Output 1

5

Giải thích

• Robot di chuyển theo lộ trình 3 → 4 → 3 → 2 → 5 → 1. Khi đi từ 3 đến 4, rồi quay lại 3 và tiếp tục đến 2, robot nhận được điểm thưởng tổng cộng là 9. Khi đi từ 2 đến 5, robot nhận một thẻ phạt và từ đó không thể nhận thêm điểm thưởng nữa.

Ràng buộc

• 30% số test có m = n - 1 nhỏ hơn 1000 và k = 0.
• 20% số test có k = 0 và n tối đa 1000.
• 20% số test có k = 0 và n tối đa 100000.
• 30% số test có k = 1.