Siêu thị bán hàng qua mạng Pacific có rất nhiều chi nhánh phục vụ và có nhiều phương tiện giao hàng tiên tiến nhanh chóng bằng thiết bị bay tự động, ngoài ra siêu thị thường có các chương trình khuyến mãi hấp dẫn vì vậy thu hút được một số lượng lớn khách hàng.

Alice vào trang Web của cửa hàng, chọn được \(n\) món hàng đưa vào danh sách các thứ sẽ mua, món hàng thứ \(i\) có giá \(a_i, i = 1 ÷ n\). Khi Alice chuẩn bị chuyển danh sách hàng đã chọn vào giỏ mua thì xuất hiện thông báo về một chương trình khuyến mãi mới. Nếu giỏ hàng mua của khách có từ 10 đến 19 mặt hàng thì món hàng giá thấp nhất trong số đó sẽ được nhận miễn phí, nếu giỏ hàng mua có từ 20 đến 29 mặt hàng thì hai món hàng giá thấp nhất trong số đó sẽ được nhận miễn phí, nếu giỏ hàng mua có từ 30 đến 39 mặt hàng thì ba món hàng giá thấp nhất trong số đó sẽ được nhận miễn phí . . . Tóm lại, nếu số lượng hàng mua tăng thêm 10 thì lại được miễn phí thêm một mặt hàng trong số các hàng có giá trị thấp nhất.

Alice không thể thay đổi trình tự hàng trong danh sách đã đăng ký mua nhưng có thể cắt danh sách thành các phần, mỗi phần gồm một dãy liên tiếp các hàng trong danh sách và bỏ vào một giỏ hàng riêng để nhận được chính sách ưu đãi đã nêu với giỏ hàng. Là một người giỏi tính toán, Alice nhanh chóng hoàn thành các giỏ đặt hàng để tổng chi phí phải trả cho \(n\) mặt hàng muốn mua là nhỏ nhất.

Yêu cầu:

• Hãy xác định số tiền mà Alice sẽ phải thanh toán.

Input:

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 ≤ n ≤ 10^5\)),
• Dòng thứ 2 chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(1 ≤ a_i ≤ 10^9, i = 1 ÷ n\)).

Output:

• Một số nguyên là số tiền ít nhất cần thanh toán.

12
1 1 10 10 10 10 10 10 9 10 10 10

92

Nguồn: 2019 CLQĐ-BĐ