Hai phiên bản chỉ khác nhau mỗi tên và giới hạn

Đoàn Nab hiện đang không biết làm sao để tiêu hết tiền của mình, anh ấy bèn rải tiền của mình lên mặt bàn, có thể hình dung như mảng gồm ~n~ giá trị ~a_1, a_2, ..., a_n~ với ~a_i~ là giá tiền của một cụm tiền. Và cho phép Trịnh Ũv của mình lấy các cụm tiền này theo quy tắc sau:

Ban đầu số tiền mà Trịnh Ũv đang lấy được ~x = 0~, (thực hiện với số lần tùy ý):

• Chọn một cụm tiền ~i~ nếu cụm đó chưa được lấy.
• Nếu cụm tiền đó có giá trị lớn hơn giá trị ~x~ hiện tại, thì Trịnh Ũv có thể nhận được số tiền này (~x = x + a_i~) và sau đó cụm tiền đó coi như là đã được lấy.

Nếu là Trịnh Ũv, bạn có thể lấy nhiều nhất bao nhiêu tiền?

Input

• Dòng đầu tiên là một số nguyên ~n~, mô tả số lượng cụm tiền.
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ mô tả giá của cụm tiền thứ ~i~.

Output

• Một dòng duy nhất là kết quả.

Constraints

• ~1\le n \le 2 \cdot 10^3~
• ~1 \le a_i \le 2 \cdot 10^3~

Input Sample 1

4
1 1 3 3

Output Sample 1

4

Input Sample 2

5
1 6 4 3 2

Output Sample 2

11