Quân đội

Lục địa QT có tổng cộng \(N\) đất nước (được đánh số từ \(1\) đến \(N\)) và có \(M\) con đường hai chiều nối giữa các đất nước với nhau. Đất nước RoNE có chỉ số là \(1\), và đất nước NhaNTH có chỉ số là \(N\). Quân đội của đất nước RoNE có \(X\) quân lính và đang muốn xuất quân đi đánh chiếm đất nước thực dân NhaNTH.

Ở mỗi đất nước trên lục địa QT đều có quân thực dân của đất nước NhaNTH chiếm đóng (kể cả đất nước của RoNE), đất nước thứ \(i\) có \(A_i\) quân thực dân. Khi đội quân của RoNE đi qua một đất nước, sẽ có một trận chiến xảy ra. Nếu số lượng quân của RoNE nhiều hơn số lượng quân thực dân tại đất nước đó, quân đội RoNE sẽ toàn thắng, chiếm được đất nước đó và không có thiệt hại nào. Ngược lại, đội quân RoNE vẫn sẽ chiến thắng và chiếm được đất nước đó nhưng số lượng quân sống sót chỉ còn một nửa (nếu số lượng quân lính của RoNE là \(x\) thì sẽ chỉ còn lại \(\lfloor \frac{x}{2}\rfloor\)). Đội quân RoNE cần phải bắt đầu từ đất nước của mình đến đất nước NhaNTH và tiêu diệt tất cả quân thực dân trên đường đi.

Nếu bạn là quân sư của đất nước RoNE, hãy tìm một đường hành quân tốt nhất sao cho có thể bảo toàn được nhiều quân lính nhất có thể sau khi chiếm được đất nước NhaNTH.

Input

• Dòng đầu tiên gồm \(2\) số \(N,M\) là số lượng đất nước và số lượng đường đi giữa các đất nước.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) mô tả một con đường nối giữa hai đất nước \(u\) và \(v\).
• Dòng tiếp theo chứa số nguyên \(X\ (1\le X\le10^9)\) là số lượng quân lính của đất nước RoNE.
• Dòng tiếp theo chứa \(N\) số nguyên dương mô tả dãy \(A\ (1\le A_i\le10^9)\) là số lượng quân thực dân tại mỗi đất nước.

Output

• Ghi ra số lượng quân lính tối đa có thể sống sót sau khi chiếm được đất nước NhaNTH. Nếu không thể chiếm đánh thành công, ghi ra \(0\).

Example

4 4
1 2
1 3
2 4
3 4
7
10 2 3 1

3

4 4
1 2
1 3
2 4
3 4
7
10 3 3 1

0

Scoring

• Subtask \(1\) (\(20\%\) số điểm) \(1 \le N,M \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm) \(1 \le N,M \le 100000\).
• Subtask \(3\) (\(50\%\) số điểm) \(1 \le N, M \le 500000\).