Michael and Charging Stations

마이클은 최근 도시를 돌아다니기 위해 새 전기 자동차를 샀다. 마이클은 과로하는 것을 좋아하지 않으므로, 매일 자신의 두 직장 중 하나에만 차를 몰고 간다.

마이클의 하루는 직장에 갔다가 돌아오기 위해 전기 자동차를 충전하는 것으로 시작한다. 첫 번째 직장에 가면 충전에 1000벌을 쓰고, 두 번째 직장에 가면 2000벌을 쓴다.

그가 이용하는 충전소에는 보너스 카드가 포함된 포인트 제도가 있다. 보너스 카드에는 음이 아닌 양의 보너스 벌이 들어 있을 수 있다. 고객이 가격이 x벌인 무언가를 구매할 때마다, 보너스 카드 잔액을 초과하지 않는 y (0 ≤ y ≤ x)벌을 보너스 벌로 결제할 수 있다. 이 경우 현금으로 x - y벌을 지불하고, 보너스 카드 잔액은 y보너스 벌만큼 감소한다.

고객이 전체 가격을 현금으로 지불하면 (i.e., y = 0), 가격의 10%가 보너스 카드로 반환된다. 즉, 보너스 카드 잔액이 보너스 벌만큼 증가한다. 처음에 보너스 카드 잔액은 0보너스 벌이다.

마이클은 앞으로 n일을 계획했으며, 각 날짜의 충전 비용을 알고 있다. Help Michael 보너스 카드를 최적으로 사용했을 때 그가 현금으로 지출해야 하는 최소 벌 금액을 구한다. 마이클은 어느 날이든 가격의 어떤 부분도 현금으로 지불할 수 있다고 가정한다. 주어진 기간이 끝날 때 모든 보너스 벌을 쓸 필요는 없다.

입력의 첫 번째 줄에는 마이클이 계획한 날짜의 수인 정수 n (1 ≤ n ≤ 300 000)이 하나 주어진다.

다음 줄에는 n개의 정수 a1, a2, ..., an (ai = 1000 or ai = 2000)이 주어지며, ai는 i번째 날의 충전 비용을 나타낸다.

마이클이 지출해야 하는 최소 벌 금액을 출력한다.

첫 번째 예제에서 마이클에게 가장 최적인 방법은 첫 이틀 동안 3000벌을 지불하고 300보너스 벌을 돌려받는 것이다. 그 후 셋째 날에는 나머지 가격을 보너스 벌로 충당하여 700벌만 지불할 수 있다.

두 번째 예제에서 마이클에게 가장 최적인 방법은 첫 닷새 동안 전체 가격을 지불하여 1000보너스 벌을 돌려받고, 마지막 날에는 현금을 전혀 지불하지 않고 이를 사용하는 것이다.