挖金币游戏

金币游戏"/>

挖金币游戏

这天，小X幸运地获得了一次进行挖金币游戏的机会，规则如下：

在一个N*N的矩形里，有N*N个边长为1的正方形格子。在游戏中取左下角的格子坐标为(1,1)，右上角为(N,N)。在游戏开始前，每一个格子中都会放入一枚金币，而当游戏开始时，每一个格子中的那一枚金币都会进行一次移动，移动后的横、纵坐标值将分别变为原横、纵坐标值每一位上的乘积。当有金币被移动出格子矩形时，将被游戏方收走。小X将被允许选取M个格子，他将获得他所选取的格子中所有的金币，而他对游戏中获得的金币数有一个期望值H。他想知道他最多能获得的金币数能否达到他的期望值。不过金币移动的让人眼花缭乱，小X算不过来了，他找到了你，希望你能用编程解决这个问题。

一行，三个正整数数N、M、H，以空格隔开，意义如题目中所述。

一个或两个正整数数，以空格隔开。

若小X最多能获得的金币数能达到期望值（即大于等于），则输出小X最多能获得的金币数以及金币总数能达到期望值的格子数的最小值。

若小X最多能获得的金币数不能达到期望值（即小于），则输出金币数最多的那个格子中的金币数。

17 3 10

12 3

对于20%的数据，保证0 ＜ M ≤ N ≤ 100；

对于50%的数据，保证0 ＜ M ≤ N ≤ 2000；

对于70%的数据，保证0 ＜ M ≤ N ≤ 5000；

对于100%的数据，保证0 ＜ M ≤ N ≤ 10000；

举例，(123,456)处的金币将会被移动至(1*2*3,4*5*6)即(6,120)。