Bo đang chơi một game. Ban đầu, Bo có một vòng tròn bán kính ~k~. Trên màn hình game còn có ~n~ vòng tròn khác, vòng tròn thứ ~i~ có bán kính là ~A_i~. Bo có thể điều khiển vòng tròn của mình để chạm vào các vòng tròn khác. Mỗi khi vòng tròn của Bo chạm vào một vòng tròn khác thì một trong hai khả năng có thề xày ra:
- Nếu bán kính vòng tròn do Bo điều khiển lớn hơn hay bằng bánh kính vòng tròn chạm vào thì vòng tròn bị chạm sẽ tan vỡ, còn vòng tròn của Bo trở nên lớn hơn và bán kính của nó sẽ bằng tổng bán kính vòng tròn hiện tại của Bo với bán kính vòng tròn bị chạm đó.
- Nếu bán kính vòng tròn do Bo điều khiển nhỏ hơn bán kính vòng tròn bị chạm vào thì kết thúc game.
Bo chơi game rất giỏi. Bạn ấy luôn tìm cách chơi sao cho khi kết thúc game thì bán kính vòng tròn của bạn ấy là lớn nhất. Theo em, bán kính lớn nhất đó là bao nhiêu?
Dữ liệu vào
Đọc từ file CIRCLE.INP
gồm hai dòng:
- Dòng thứ nhất: gồm hai số nguyên dương lần lượt là ~n~ và ~k~. Trong đó, ~n~ là số lượng vòng tròn, ~k~ là bán kính vòng tròn của Bo, giữa ~n~ và ~k~ được cách nhau bởi một dấu cách.
- Dòng thứ hai: gồm ~n~ số nguyên dương ~A_i~, lần lượt là bán kính của ~n~ vòng tròn, giữa các số được cách nhau bởi một dấu cách.
Kết quả ra
Ghi ra file CIRCLE.OUT
một số nguyên dương là bán kính lớn nhất cần tìm.
Giới hạn
~1 \le n \le 10^3~, ~1 \le k \le 10^6~, ~1 \le A_i \le 10^6~, ~1 \le i \le n~.
Ví dụ
Dữ liệu
5 4
7 68 3 2 20
Kết quả
16
Giải thích
Ban dầu, có ~5~ vòng tròn (~n = 5~) với bán kính lần lượt là ~7, 68, 3, 2, 20~ và vòng tròn của Bo có bán kính là ~k = 4~.
Lần 1: Vòng tròn của Bo chạm vòng tròn có bán kính là ~2~ ~\rightarrow~ vòng tròn của Bo có bán kính mới là ~4 + 2 = 6~.
Lần 2: Vòng tròn của Bo chạm vòng tròn có bán kính là ~3~ ~\rightarrow~ vòng tròn của Bo có bán kính mới là ~6 + 3 = 9~.
Lần 3: Vòng còn của Bo chạm vòng tròn có bán kính là ~7~ ~\rightarrow~ vòng tròn của Bo có bán kính mới là ~9 + 7 = 16~.
Dến đây, còn hai vòng tròn có bán kính là ~20~ và ~68~. Hai bán kính này đều lớn hơn bán kính vòng của Bo nên kết thúc game.
Vậy bán kính lớn nhất cần tìm là ~16~.
Comments