(robot_vt.*)

Một cuộc thi lập trình điều khiển robot được ban tổ chức olympic 30-4 thiết kế cho các bạn yêu thích Tin học. Ban tổ chức thiết kế một sơ đồ cho robot di chuyển gồm \(n\) địa điểm được đánh số từ 1 tới \(n\) và được nối với nhau bởi \(m\) con đường hai chiều, đánh số từ 1 tới \(m\). Con đường thứ \(i\) nối hai địa điểm \(u_{i}\) và \(v_{i}\) với trọng số \(w_{i}(1 \leq u_{i},v_{i} \leq n;w_{i} \leq 10^{9})\). Tại mỗi địa điểm ghi một số nguyên \(a_{i}\ \)là số điểm thưởng mà robot nhận được khi đến địa điểm này lần đầu\(.\)

Ban tổ chức chọn một địa điểm \(s\) làm địa điểm xuất phát và robot nhận được điểm thưởng đầu tiên tại địa điểm này. Mỗi khi đi qua con đường có trọng số lớn hơn điểm thưởng đang có, robot sẽ nhận một thẻ phạt. Robot được phép bị phạt không quá \(k\) thẻ. Khi bị phạt thẻ, robot sẽ không được phép nhận thêm điểm thưởng ở bất kỳ địa điểm nào nữa.

Yêu cầu: Hãy xác định số địa điểm lớn nhất mà robot có thể đi qua.

Dữ liệu vào:

• Dòng đầu tiên chứa 4 số nguyên \(n,m,s\) và \(k(1 \leq n \leq 10^{5};1 \leq m \leq 2 \times 10^{5}\); \(1 \leq s \leq n;k \leq 1)\);

• Dòng thứ hai chứa \(n\ \)số nguyên\(\ a_{1},\ a_{2},\ldots,\ a_{n}\ \left( 1 \leq a_{i} \leq 10^{9} \right)\);

• Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa 3 số nguyên \(u_{i},\ v_{i}\) và \(w_{i}\) \((1 \leq u_{i}
  eq v_{i} \leq n;1 \leq w_{i} \leq 10^{9})\).

Kết quả:

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

Ví dụ:

Input	Output	Minh hoạ
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	5

Giải thích: Robot đi \(3 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 5 \rightarrow 1\). Robot đi \(3 \rightarrow 4 \rightarrow 3 \rightarrow 2\) nhận được điểm thưởng là \(9\). Đi từ \(2\) sang \(5\) bị nhận 1 thẻ phạt và từ đó không được nhận thêm điểm thưởng.

Ràng buộc:

• \(30\%\) số điểm có \(m = n - 1 < 10^{3};u_{i} = i;\ v_{i} = i + 1;k = 0;\)

• \(20\%\) số điểm có \(k = 0;n \leq 10^{3}\);

• \(20\%\) số điểm có \(k = 0;n \leq 10^{5}\);

• \(30\%\) số test có \(k = 1\).