행운의 승차권 timer 1s memory 128MB

정올국의 지하철 승차권은 다음과 같이 a-b의 형태로 이뤄져 있다. 여기서 a는 N이하의 양의 정수이며, b는 M이하의 양의 정수이다.

정올국에서는 승차권이 ab=rev(a)rev(b)일 경우 해당 승차권을 행운의 승차권이라고 부른다. rev(x)는 숫자 x를 뒤집은 것을 의미하며, 뒤집었을 때 앞에 붙은 0은 제거를 한다. 예를 들어, rev(12343)=34321 이고 rev(1200)=21이 된다.

새로이 정기권을 발급하기 위해 정올국은 N과 M을 결정하여 승차권을 발급하고자 한다. 단, 아래의 조건을 만족해야 한다.

 

1. N과 M을 결정하였을 경우, 가능한 모든 조합의 승차권을 발급해야한다. 가령 N = 3, M = 2라고 할 경우 "1-1", "1-2", "2-1", "2-2", "3-1", "3-2"의 승차권이 발급되어야 한다. 동일한 조합의 승차권이 두번이상 발급 되는 경우는 존재하지 않는다.

 

2. N은 maxN 이하의 양의 정수여야 하며, M은 maxM이하의 양의 정수여야 한다.

 

3. 발급되는 승차권 중에서 적어도 W개의 행운의 승차권이 존재해야 한다.

 

4. 1,2,3을 만족할 때, 발급되는 모든 조합의 승차권의 수가 최소가 되어야 한다.

maxN, maxM 그리고 W가 주어졌을 때, 위의 모든 조건을 만족하는 N과 M을 구하는 프로그램을 작성하라.