마법 수리공 timer 1.5s memory 512MB

판타지세계에 사는 수리공 창하는 마법을 이용하여 손님들의 물품들을 수리해 주고 돈을 받는다.

창하는 이 세계관에서 물건 수리하는 일을 제일 잘 하기 때문에(다른 수리공들은 마법을 쓰지 못한다) 인기가 매우 많다.

그러므로 손님들은 항상 줄을 서서 수리를 받는다. 현재 N명이 줄을 서 있다.

물품 종류에 상관없이 수리하는 일은 항상 1분이 걸린다. 따라서 모든 일이 진행되는데는 총 N분이 걸린다.

좋은 물품일수록 수리하는데 사용하는 “마법력”이 많이 든다. 또한 그만큼 수리비도 많이 받을 수 있다.

구체적으로, i번째 손님의 물품의 가치는 C_i이다. 창하가 이 물품을 수리하는데는 C_i만큼의 마법력이 들며, 그 보상으로 받는 돈도 C_i원이다.

모든 손님들의 요구를 다 들어주면, 창하의 마법력이 너무 빨리 바닥나기 때문에, 창하는 i번째 손님을 맞이함에 있어서 다음 두 가지 중 한 가지 행동을 할 수 있다.

1. C_i의 마법력을 들여서 물품을 수리해주고, C_i원을 받는다.

2. 그 손님을 그냥 집으로 보내버리고, “미안” 한마디정도 던져준다(그 손님은 화가 많이 나겠지만, 괜찮다. 어차피 뒤에 돈 내고 수리하기 위한 손님들은 많다.)

   창하는 이 순간 곧바로 다음 손님을 받는 것이 아니라 1분간 명상하면서 마법력을 회복한다. 이 1분 동안 창하는 M의 마법력을 회복할 수 있다. (참고로 마법력은 최대치가 없으므로, 명상만 많이 한다면 얼마든지 늘어난다.)

   명상 후, 창하는 다음 손님을 맞이한다.

처음에 창하의 총 마법력은 K이다.

줄을 서 있는 N명의 손님이 수리해야 할 물건이 순서대로 주어졌을 때, 창하가 물품을 수리하여 받을 수 있는 금액의 최대치를 구하는 프로그램을 작성하라.