Thẻ tích điểm trạm sạc

Michael vừa mua một chiếc ô tô điện. Mỗi ngày anh chỉ đi tới một trong hai nơi làm việc, và buổi sáng anh phải sạc xe: nếu đi tới nơi làm việc thứ nhất thì chi phí sạc là $1000$ burle, còn nếu đi tới nơi thứ hai thì chi phí là $2000$ burle.

Trạm sạc có chương trình tích điểm bằng thẻ thưởng. Thẻ thưởng lưu một số nguyên không âm điểm thưởng (mỗi điểm thưởng tương đương $1$ burle). Khi phải thanh toán một khoản $x$ burle, Michael được chọn một số nguyên $y$ với $0\le y\le x$ và $y$ không vượt quá số dư hiện tại của thẻ: khi đó anh trả $x-y$ burle tiền mặt và số dư thẻ giảm đi $y$ điểm.

Điểm thưởng chỉ được cộng khi Michael trả toàn bộ khoản tiền bằng tiền mặt: nếu $y=0$ thì sau lần thanh toán đó số dư thẻ tăng thêm $\frac{x}{10}$ điểm (tức $10\%$ giá trị đơn hàng). Nếu $y>0$ thì lần thanh toán đó không được cộng điểm nào.

Ban đầu số dư thẻ bằng $0$. Michael đã lên kế hoạch cho $n$ ngày tới và biết chi phí sạc của từng ngày. Hãy giúp anh xác định tổng số tiền mặt ít nhất phải chi ra nếu sử dụng thẻ thưởng một cách tối ưu. Không bắt buộc phải dùng hết điểm thưởng vào cuối kỳ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số ngày trong kế hoạch.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$, trong đó $a_i$ là chi phí sạc của ngày thứ $i$.

Dữ liệu ra

Một số nguyên duy nhất là tổng số tiền mặt nhỏ nhất Michael phải chi.

Ràng buộc

• $1\le n\le 300000$
• $a_i\in \{1000,2000\}$

Ví dụ