Có ~2n~ bạn đi tham quan đánh số từ ~1~ tới ~2n~, bạn thứ ~i~ có trọng lượng là ~w_i~. Những bạn này muốn thuê ~n~ xe đạp giống nhau, sau đó chia làm ~n~ nhóm, mỗi nhóm gồm 2 người đi trên một xe đạp. Vì các xe đạp giống nhau nên nó sẽ có cùng giới hạn tải trọng (đây là một số đo trọng lượng mà xe không thể chở quá giới hạn trọng lượng đó), xe đạp có giới hạn tải trọng càng lớn thì giá thuê càng đắt.
Yêu cầu
Hãy giúp các bạn chọn loại xe có giới hạn tải trọng nhỏ nhất mà vẫn có thể thực hiện chuyến tham quan bằng xe đạp.
Dữ liệu
- Dòng 1 chứa số nguyên dương ~n~ \((n \leq ~10^5~)\).
- Dòng 2 chứa ~2n~ số nguyên dương ~w_1,w_2,…,w_{2n}~ \((∀i:~w_i~ \leq ~10^{18}~)\) cách nhau bởi dấu cách.
Kết quả
Một số nguyên duy nhất là giới hạn tải trọng nhỏ nhất của loại xe đạp cần thuê.
Input
3
1 4 2 8 6 7
Output
10
Giải thích về cách đi khi thuê xe có giới hạn tải trọng 10
Nhóm 1: Người 1 + Người 4, trọng lượng 9.
Nhóm 2: Người 2 + Người 5, trọng lượng 10.
Nhóm 3: người 3 + Người 6, trọng lượng 9.
Bình luận