Sự bất mãn của các tài xế

Một vương quốc có $n$ thành phố và $m$ con đường hai chiều. Con đường thứ $i$ nối hai thành phố $a_i,b_i$, mang mức độ phàn nàn của tài xế là $w_i$.

Mỗi con đường còn có một chỉ số $c_i$ — số lamzik cần chi để giảm mức phàn nàn của đường đó đi $1$ đơn vị. Như vậy để giảm phàn nàn của đường thứ $i$ đi $k$ đơn vị thì cần tốn $k·c_i$ lamzik. $k$ phải là một số nguyên không âm; mức phàn nàn sau khi giảm có thể bằng $0$ hoặc thậm chí âm.

Bộ Giao thông có ngân sách $S$ lamzik. Ngân sách sẽ được dùng để giảm phàn nàn trên một số con đường, sau đó họ phải chọn $n-1$ con đường làm đường chính sao cho từ thành phố bất kỳ có thể đi đến thành phố khác chỉ qua các đường chính (tập đường chính tạo thành cây khung).

Hãy phân bổ ngân sách và chọn $n-1$ đường chính sao cho tổng mức phàn nàn của các đường chính là nhỏ nhất. Không bắt buộc phải tiêu hết ngân sách $S$. Bảo đảm rằng đồ thị ban đầu liên thông; cho phép tồn tại nhiều cạnh giữa cùng một cặp thành phố.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ ($2\le n\le 2·{10}^5$, $n-1\le m\le 2·{10}^5$).
• Dòng thứ hai chứa $m$ số nguyên $w_1,w_2,\dots ,w_m$ ($1\le w_i\le {10}^9$).
• Dòng thứ ba chứa $m$ số nguyên $c_1,c_2,\dots ,c_m$ ($1\le c_i\le {10}^9$).
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$, $b_i$ ($1\le a_i,b_i\le n$, $a_i\ne b_i$) — mô tả con đường thứ $i$.
• Dòng cuối chứa một số nguyên $S$ ($0\le S\le {10}^9$).

Dữ liệu ra

• Dòng đầu in ra $K$ — tổng mức phàn nàn nhỏ nhất có thể đạt được.
• Trên $n-1$ dòng tiếp theo, mỗi dòng in hai số $x$ và $v_x$ — chỉ số (từ $1$) của con đường được chọn làm đường chính cùng với mức phàn nàn của nó sau khi đã chi tiêu ngân sách.

Các con đường có thể được in theo thứ tự bất kỳ. Nếu có nhiều đáp án, hãy in ra một đáp án bất kỳ.

Ví dụ