Trong một đợt thanh lý hàng cũ, cửa hàng X cần bán ~n~ máy tính có cấu hình giống nhau. Có ~m~ khách hàng đồng ý mua các máy tính này, mỗi khách hàng sẽ mua 1 cái. Khách hàng thứ ~i~ (~i=1 \dots m~) sẽ đồng ý mua nếu như giá bán của mỗi chiếc máy tính không vượt quá ~P_i~. Cửa hàng cần định ra một mức giá bán sao cho tổng số tiền thu về là lớn nhất.
Ví dụ: nếu có 5 cái máy tính và có 4 khách hàng đặt mua với mức giá là ~\{2, 8, 10, 7\}~. Nếu cửa hàng định mức giá là 2 thì cả 4 người đều mua được nhưng số tiền mà cửa hàng thu được chỉ là ~2 \times 4 = 8~; Nếu cửa hàng định mức giá là 10 thì chỉ bán được cho 1 khách hàng nhưng số tiền thu được là 10; Phương án tối ưu là định giá là 7, khi đó bán được cho 3 khách hàng với số tiền thu về lớn nhất bằng ~7 \times 3 = 21~.
Dữ liệu vào: COMPUTER.INP
- Dòng đầu tiên ghi hai số nguyên dương ~n, m~ (~n, m \leq 10^5~).
- Dòng thứ hai ghi các số ~p_1, p_2, \dots, p_m~. Mỗi số có giá trị không vượt quá 1000.
Kết quả: COMPUTER.OUT
- Dòng 1: Ghi ra một số nguyên duy nhất là số tiền lớn nhất thu được.
Ví dụ:
COMPUTER.INP
5 4
2 8 10 7
COMPUTER.OUT
21
Bình luận