Tiền thưởng

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Năm nay, cuộc thi chọn học sinh giỏi Duyên Hải có một nhà tài trợ trao một phần thưởng vô cùng thú vị cho thí sinh giành giải nhất môn Tin học. Số tiền thưởng mà thí sinh nhận được chính là số điểm mà thí sinh đó lấy được trong trò chơi mà nhà tài trợ đưa ra:

Cho một dãy \(n\) số nguyên (\(a_1, a_2, …, a_n\)). Người chơi có thể thực hiện những thao tác sau đây trên dãy đã cho:

  • Chọn một số \(a_i\) bất kỳ thì nhận được số điểm là \(a_i\) (\(i = 1÷n\)).
  • Đồng thời cũng phải xóa đi tất cả các số có giá trị là (\(a_i – 1\)) và (\(a_i + 1\)) có trong dãy ngay sau đó.

Yêu cầu: Ban đầu người chơi có 0 điểm. Bạn hãy cho biết số tiền lớn nhất mà thí sinh giải nhất có thể nhận được từ nhà tài trợ.

Input

  • Dòng đầu tiên chứa một số nguyên \(n\) (\(1\le n \le 20000\))
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, …, a_n\) (\(1\le a_i \le10000\)), mỗi số cách nhau một dấu cách.

Output

  • Đưa ra một số nguyên là số tiền lớn nhất mà thí sinh giải nhất có thể nhận được.

Scoring

  • Subtask \(1\) (\(60\%\) số điểm): \(1 \le n \le 1000\), \(1\le a_i \le 100\).
  • Subtask \(2\) (\(40\%\) số điểm): \(1\le n \le 20000\), \(1\le a_i \le 10000\).

Example

Test 1

Input 
3
3 4 2
Output 
6

Test 2

Input 
6
2 2 3 3 3 4
Output 
9

Bình luận