헬스꽝 timer 1s memory 256MB

몸짱 택쌤은 오늘도 운동을 한다. 몸짱들은 언제나 그날의 운동 루틴이 있다.

오늘의 운동 루틴은 N개의 운동 프로그램으로 준비되어 있는데, 각 운동 프로그램은 제각기 운동 효과가 다르다.

택쌤이 이 N개의 모든 운동을 다 한다면, 이 모든 효과를 다 볼 수 있을 것 같지만, 

불행히도 인간의 몸은 연속으로 힘을 쓰면 지치게 되어 있다는 것.

그래서 택쌤은 불가피하게 어떤 운동 프로그램은 스킵을 해야 한다.

처음에, 컨디션 만땅의 택쌤은 총 E만큼의 에너지를 가지고 있다.

각 운동 프로그램은 a_i의 운동 효과를 가지고 있는데, 

택쌤이 a_i이상의 에너지를 가지고 있다면 그 운동을 함으로써, a_i만큼의 효과를 낼 수 있다.

하지만, a_i의 효과를 낼 수 있는 운동임에도 불구하고, 택쌤의 에너지가 e만큼 밖에 없다면, e의 효과만 낼 수 있다.

택쌤이 연속으로 운동을 할 때마다, 에너지는 k의 비율로 감소한다.

예를 들어 만땅 에너지 상태(E)에서 3개의 운동을 연속으로 했다면 3번째 운동에서의 에너지는 Ek²밖에 없는 것이다.

그러나 20대의 젊은 피 아니겠는가.

택썜이 한 운동을 스킵함으로써 조금이라도 쉬면, 다시 에너지가 E로 돌아온다. 

즉, 다음 운동의 효과를 위하여 어떤 운동은 포기할 수 있다.

택쌤은 최대한 많은 운동 효과를 보고 싶다. 

E, k와 오늘의 운동 루틴이 주어졌을 때, 최대 운동 효과를 계산하는 프로그램을 작성하라.

[부분점수의 제약 조건]

모든 입력 데이터에 있어서, 1 ≤ E ≤ 10,000, 1 ≤ N ≤ 1,000, 0 ≤ k ≤ 1, 1 ≤ a_i ≤ 30,000 을 만족한다.

부분문제 1: 전체 100점 중 10점에 해당하며, k=0.0이다.

부분문제 2: 전체 100점 중 15점에 해당하며, k=1.0이다.

부분문제 3: 전체 100점 중 10점에 해당하며, N<=20이다.

부분문제 4: 전체 100점 중 65점에 해당하며, 주어진 조건 외 아무 제약이 없다.