USACO 2022 December Contest, Bronze, Cow College

Xem PDF

Điểm: 1000 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nông dân John đang dự định mở một trường đại học mới cho các chú bò!

Có tổng cộng \(N (1 \le N \le 10^5)\) chú bò có thể dự định nhập học vào trường này. Mỗi chú bò sẵn sàng trả một mức học phí tối đa là \(c_i (1 \le c_i \le 10^6)\). Nông dân John có thể điều chỉnh học phí sao cho mọi chú bò phải trả để nhập học. Nếu mức học phí vượt mức tối đa mà một chú bò sẵn sàng chi, chú bò này sẽ không nhập học. Nông dân John muốn kiếm thật nhiều tiền để có thể trả lương cho các giảng viên một cách công bằng nhất. Hãy cho biết lượng tiền mà bác John có thể kiếm được, và lượng học phí mà bác John cần điều chỉnh.

Input

  • Dòng đầu tiên là số \(N\).
  • Dòng thứ hai là \(N\) số \(c_1, c_2, \dots, c_N\), trong đó \(c_i\).

Output

  • Lượng tiền tối đa mà bác John có thể kiếm được, và lượng học phí mà bác John cần điều chỉnh.

Scoring

  • Subtask \(1\): \(c_i \le 1000\).
  • Subtask \(2\): \(N \le 5000\).
  • Subtask \(3\): Không có thêm ràng buộc.

Test 1

Input
4
1 6 4 6
Output
12 4
Note

Nếu nông dân John thu mức học phí là \(4\) thì \(3\) chú bò sẽ nhập học, điều đó giúp bác thu được lượng tiền là \(3 \times 4 = 12\).


Bình luận

Không có bình luận nào.