Giáo sư FOS xin ứng tuyển vào một công ty công nghệ. Vào rồi mới biết hóa ra đây là công ty đa cấp.

Công ty gồm có \(N\) người được đánh số từ 1 tới \(N\). Cấu trúc nhân sự của công ty có thể hình dung như một cái cây, với gốc là Sếp tổng ở nút \(1\). Trừ ông Tổng, mỗi người đều có 1 cấp trên trực tiếp (nút cha) và các cấp dưới trực tiếp (các nút con).
Mỗi liên hệ trực tiếp trong công ty (tức mỗi cạnh trên cây) gồm hai người \(u, v\), có độ liên kết giữa hai người này sẽ là \(w\).
\(u\) được gọi là cấp trên của \(v\) nếu \(u\) là cấp trên trực tiếp của \(v\), hoặc nếu \(u\) có cấp dưới trực tiếp là cấp trên của \(v\).

Công ty chuẩn bị tổ chức sự kiện team-building "Làm giàu không khó", và cần chia các thành viên thành các nhóm. Biết rằng Giáo sư FOS nghiên cứu rất nhiều về thuật toán, nên Tổng nhờ Giáo sư xử lý giúp.

Mỗi nhóm được chia để khi nhìn trên cây, đó sẽ là một đường đi từ đỉnh \(u\) tới đỉnh \(v\), sao cho \(u\) là cấp trên của \(v\). Hơn nữa, tổng độ liên kết của các cạnh trên đường đi đều không quá \(K\).
Ngoài ra, giáo sư được phép dùng \(M\) cách chia nhóm đặc biệt, mỗi cách biểu thị bởi một bộ chỉ số \((u, v)\). Với cách chia này, ta sẽ gộp các đỉnh trên đường đi đơn từ \(u \rightarrow v\) thành một nhóm. \(u, v\) không nhất thiết phải có mối quan hệ cấp trên/dưới với nhau.

Giáo sư lỡ bận làm đề thi Sơ loại Olympic MT-TN mất rồi. Bạn hãy giúp giáo sư cho biết số nhóm ít nhất để chia toàn bộ cây sao cho mỗi nút trên cây thuộc đúng một nhóm.

Input

• Dòng đầu tiên lần lượt chứa 3 số \(N, M, K\) \((1 \le N, M \le 10^5, 1 \le K \le 10^{14})\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa ba số \(u[i], v[i], w[i]\) biểu thị hai đỉnh và trọng số của cạnh thứ \(i\) \((1 \le w[i] \le 10^9)\).
• \(M\) dòng cuối cùng, mỗi dòng chứa hai số \(u, v\) biểu thị hai đỉnh của một cách chia nhóm đặc biệt.

Output

In ra một số nguyên dương là kết quả của bài toán.

Ví dụ

Input

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

Output

3

Subtask

• Subtask 1(20%): \(1 \le N, M \le 10^3\)
• Subtask 2(20%): Cây có dạng một đường thẳng
• Subtask 3(28%): \(1 \le N \le 10^5, M = 0\)
• Subtask 4(32%): \(1 \le N, M \le 10^5\)