문제

아람이가 학술부장 자리를 찬탈한 데 이어, 알로하 회장님까지 납치했다! 아람이는 알로하 회원 모두가 인당 만원씩 보낸다면 회장님을 풀어준다고 공표했다.

회원들은 각자 회장님을 존경하는 만큼 송금할 것이다. 이때 만약 이전 사람이 만원보다 적은 금액을 송금했다면, 이후 사람이 만원에 그 차액을 더한 만큼 송금해야 한다. 단, 이전 사람이 내야 할 돈보다 많은 돈을 송금했다고 해도 다음 사람이 내야 할 돈이 만원보다 작아지지는 않는다.

예를 들어, 첫 번째 사람이 만원을 보냈다면 다음 두 번째 사람은 만원이 아닌 만원을 보내야 한다. 여기서 만약 두 번째 사람이 만원이 아닌 만원만 보냈다면, 세 번째 사람은 만원을 보내야 한다. 이 때 세 번째 사람이 만원을 보냈다고 해도 네 번째 사람은 만원만 보내면 된다.

인사부장 예원이는 가장 마지막 순서로 자원해 책임지고 회장님을 구출하기로 했다. 예원이는 돈을 최대한 적게 쓰고 싶었기 때문에, 인사부장의 힘으로 회원들의 송금 예정액을 미리 조사한 뒤 자신이 가장 돈을 적게 낼 수 있는 순서대로 송금하도록 회원들을 협박하려고 한다. 협박에 성공했을 때 예원이가 납치범 아람이에게 보내야 하는 금액을 구해보자.

입력

첫째 줄에 예원이를 제외한 알로하 회원 수를 뜻하는 정수 이 주어진다. ()

둘째 줄에 정수 이 공백으로 구분되어 주어진다. 는 번째 회원이 송금할 금액을 의미한다. ()

출력

첫째 줄에 예원이가 납치범 아람이에게 보내야 할 금액을 출력한다.