Làm bài tập về nhà


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

An và Bình cùng làm bài tập về nhà. Mỗi bạn cần hoàn thành $N$ bài tập. Mỗi bạn cần dành $a_i$ phút để làm bài $i$. Vì mỗi bài tập là một tờ đề nên hai bạn không thể làm chung một bài trong một thời điểm.

Hãy tìm cách phân chia sao cho tổng thời gian hoàn thành bài của hai bạn là nhỏ nhất.

Dữ liệu

  • Dòng đầu tiên chứa số nguyên $N \ (0<N \le 10^5)$;
  • Dòng tiếp theo chứa $N$ số nguyên $a_i \ (0< a_i \le 10^9)$;

Kết quả

  • Thời gian hoàn thành nhỏ nhất.

Ví dụ

Ví dụ 1

input

4
1 2 3 7

output

14

Comments

There are no comments at the moment.