Du lịch

Alex chuẩn bị một chuyến du lịch trong một đất nước có $n$ thành phố và $m$ con đường hai chiều nối các thành phố. Mỗi thành phố $i$ được gán điểm hấp dẫn $w_i$. Alex hiện đang ở thành phố $s$ và muốn lên kế hoạch hành trình sao cho tổng điểm hấp dẫn của tập các thành phố từng được ghé thăm là lớn nhất (mỗi thành phố chỉ được tính điểm một lần, kể cả khi ghé nhiều lần).

Hành trình phải thoả mãn: Alex không bao giờ đi qua hai lần liên tiếp cùng một con đường. Nghĩa là nếu Alex vừa đi từ $u$ đến $v$, thì bước tiếp theo phải đi đến một thành phố khác $u$ (nhưng có thể quay lại $u$ sau đó qua một đường khác).

Đảm bảo đồ thị liên thông, không có cạnh khuyên, không có cạnh bội.

Dữ liệu vào

• Dòng đầu: hai số nguyên $n$ và $m$.
• Dòng thứ hai: $n$ số nguyên $w_1,w_2,\dots ,w_n$.
• $m$ dòng tiếp theo: mỗi dòng hai số $u,v$ — một con đường nối $u$ và $v$.
• Dòng cuối: một số nguyên $s$ — thành phố xuất phát.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng điểm lớn nhất Alex có thể thu được.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $0\le m\le 2·{10}^5$
• $0\le w_i\le {10}^9$
• $1\le u,v\le n$
• $1\le s\le n$

Ví dụ