겨울 축제
시간 제한2초메모리 제한1024 MB
감동 수치 i인 팀은 K^i의 감동을 주며, 최대 M개의 축제에 같은 크기의 감동을 배분할 때 한 축제가 받는 최대 감동을 K진법으로 구한다.
문제
민철이는 국내 최고의 공원인 'Minchul Park'의 설립자이자 주인이다. 민철이는 다가오는 겨울 시즌을 기념하여 공원에서 개의 축제를 개최할 예정이다. 축제가 일어난다는 소식을 들은 전국 각지의 수많은 팀들이 Minchul Park에서 공연하기 위해 오디션에 참가했다. 민철이는 오디션 결과에 따라 각 팀에 '감동 수치'를 부여했다. 각 팀의 감동 수치는 이상 이하의 정수이다. 감동 수치가 인 팀은 관객들에게 만큼의 감동을 줄 수 있다. 민철이는 다음 두 조건을 만족하도록 개의 축제에 이 팀들을 적절히 배치하려고 한다.
- 각 축제에서 주는 감동의 크기는 같아야 한다.
- 한 팀은 최대 하나의 축제에서만 단 한 번 공연할 수 있다. 두 조건을 모두 만족시키려면 공연하지 못하는 팀이 생길 수 있다.
이 때, 하나의 축제에서 줄 수 있는 감동의 최대 크기를 구하여라.
입력
첫 번째 줄에는 세 정수 가 공백으로 구분되어 입력된다.
두 번째 줄에는 '감동 수치'가 인 팀의 수인 가 입력된다.
출력
하나의 공연에서 선사할 수 있는 최대의 감동을 진법으로 한 줄에 출력한다. 만약 이상의 감동을 선사할 방법이 없다면 을 출력한다. 이 경우를 제외하면 출력은 으로 시작하지 않아야 한다.