자전거 경주
시간 제한2초메모리 제한512 MB
라이더 N명이 각각 에너지 E를 가지고 D랩 경주를 완주할 때, 선두를 교대하며 에너지를 분배해 완주에 걸리는 최소 정수 시간을 구하는 문제입니다.
문제
자전거 팀에는 N(1 <= N <= 20)명의 주자가 있다. 팀은 가능한 한 이른 정수 분에 결승선에 도착하는 전략을 세우려 한다.
주자들은 혼자 달리지 않고 함께 달릴 수 있다. 어느 1분 동안 팀이 x바퀴/분의 속력으로 달리면, 맨 앞 주자는 그 1분 동안 x*x의 에너지를 쓰고 나머지 함께 달리는 주자들은 각각 x의 에너지를 쓴다. 여기서 x는 양의 정수이다. 선두 주자는 매 분이 끝날 때 바꿀 수 있으며, 교체에는 시간이나 에너지가 들지 않는다. 주자는 경주 도중 포기할 수 있고, 포기한 뒤에는 더 이상 달리지 않는다.
트랙은 총 D(1 <= D <= 100)바퀴이다. 모든 주자는 E(1 <= E <= 100)의 에너지를 가지고 출발한다. 결승선을 통과하는 주자는 한 명이면 충분하다.
경주를 마칠 수 있는 가장 이른 정수 시간을 구하라. 어떤 1분 구간의 도중에 D바퀴를 넘더라도, 그 구간을 끝까지 달릴 에너지가 필요하며 완료 시간은 그 다음 정수 분으로 계산된다.
입력
첫 줄에 세 정수 N, E, D가 주어진다.
출력
팀이 경주를 마칠 수 있는 가장 이른 정수 시간을 출력한다. 에너지가 부족하여 어떤 방법으로도 경주를 마칠 수 없다면 0을 출력한다.