~Nana~ và ~Zinno~ đang tham gia vào một cuộc phiêu lưu hấp dẫn trong trò chơi MMORPG. Hôm nay, họ có nhiệm vụ thám hiểm một hầm ngục bí ẩn với cấu trúc đặc biệt. Nhiệm vụ của họ không giống nhau:

• ~Nana~: Bắt đầu từ tầng ~1~ và thu thập điểm kinh nghiệm nhiều nhất có thể. Cô sẽ di chuyển đến các tầng liên kết và tiếp tục cho đến khi không thể đi tiếp nữa.

• ~Zinno~: Bị dịch chuyển vào một tầng ngẫu nhiên ~z~, ~Zinno~ phải tìm đường nhanh nhất về tầng ~1~ để hoàn thành nhiệm vụ.

Tuy nhiệm vụ khác nhau nhưng họ lại cùng làm nhiệm vụ trên môt hầm ngục,với cấu trúc như sau:

• Hầm ngục này có ~n~ tầng và ~n-1~ cầu thang, tạo thành một cấu trúc giống như đồ thị cây.
• Các tầng được kết nối với nhau thông qua các cầu thang, mỗi cầu thang nối hai tầng lại với nhau.
• Mỗi tầng có thể liên kết với nhiều tầng khác thông qua cầu thang, nhưng không có chu kỳ, tức là không có đường nào quay lại chính nó.

Dưới đây là một số quy tắc đặt ra của cả hai nhiệm vụ là như sau:

• Điểm kinh nghiệm: Mỗi lần ~Nana~ hoặc ~Zinno~ đi vào tầng ~i~, họ sẽ nhận hoặc mất một lượng điểm kinh nghiệm ~exp_i~, nếu ~exp_i~ ~>~ 0 thì đó là điểm kinh nghiệm họ nhận được, ngược lại ~exp_i~ ~<~ 0 thì đó là số kinh nghiệm cần trả của tầng đó. Nếu một tầng đã có người nhận hoặc trả điểm kinh nghiệm, người đến sau sẽ không nhận hoặc phải trả nữa.

• Chia sẻ điểm kinh nghiệm: Nếu cả hai cùng đến một tầng, điểm kinh nghiệm sẽ được chia đều, cụ thể là mỗi người được nhận ~\lfloor \frac{exp_i}{2} \rfloor~.

• Không quay lại: Cả ~Nana~ và ~Zinno~ không thể quay lại các tầng đã đi qua.

~Zinno~ không quan tâm điến điểm kinh nghiệm mà chỉ cần hoàn thành nhiệm vụ,còn ~Nana~ thì muốn điểm kinh nghiệm là lớn nhất có thể.

Bạn hãy xác định xem ~Nana~ có tối đa bao nhiêu điểm kinh nghiệm

Input

Dòng đầu tiên là 2 số nguyên dương ~n,q~ ~(2 \le n,q \le 10^5, 2 \le z \le n )~

Dòng tiếp theo gồm ~n~ số nguyên ~exp_i~ ~-~ là điểm kinh nghiệm của cửa tầng đó ~(-10^9 \le exp_i \le 10^9)~

~n-1~ dòng cuối, mỗi dòng gồm ~2~ số nguyên dương ~u,v~ ~(u \neq v , 1 \le u,v \le n)~ ~-~ thể hiện có cầu thang nối giữa tầng ~u~ và ~v~

Output

In ra số điểm kinh nghiệm tối đa mà ~Nana~ nhận được

Sample Input

5 4
-2 4 2 -4 6
1 2
2 3
2 4
4 5

Output

6

Giải thích

Như hình trên:

-Ban đầu ~Nana~ ở tầng ~1~, ~Zinno~ ở tầng ~4~. Họ phải trả điểm kinh nghiệm của các tầng tương ứng của họ.

Điểm kinh nghiệm của ~Nana~ bây giờ là ~-2~.

• Cả ~Nana~ và ~Zinno~ đều di chuyển đến tầng ~2~. Vì họ đến đây cùng lúc, nên họ cùng mở tầng đó và chia sẻ điểm.

  Điểm kinh nghiệm của ~Nana~ trở thành ~-2 + \frac{4}{2}~ ~= 0~.

• ~Nana~ di chuyển đến tầng ~4~. Vì ~Zinno~ đã trả điểm của tầng này, nên thu nhập của ~Nana~ không đổi.

  ~Zinno~ di chuyển đến tầng ~1~ và dừng lại.

• ~Nana~ di chuyển đến tầng ~5~ và mở cổng ở đó. Điểm kinh nghiệm của cô ấy trở thành ~0 + 6 = 6~.