MUV LUV EXTRA

Time Limit: 2000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1817 Accepted Submission(s): 348

Problem Description

鉴纯夏是一名成绩不太好的高中生。一天她在数学考试中碰到了一道求某条线段长度的问题。因为她并不会做这道题，所以她准确地作图后用尺子量出了这条线段的长度。不幸的是，答案在10进制下为一个无限小数，纯夏只量出了这个无限小数在$10$进制表示下的前若干位。

纯夏猜测问题的答案为一个有理数，所以答案为一个无限循环小数，如$\frac{1}{3}=0.333\cdots,\frac{36}{35}=1.0285714285714\cdots$。纯夏希望从这个无限小数的前$n$位猜出原本的数字。纯夏意识到，猜测的循环节太长或循环节已经开始出现的部分长度太短是不可信的。举个例子，若她量出的小数为$1.0285714285714$，显然假设循环节为$0285714285714$（长度为$13$）或假设循环节为$428571$（已经开始出现的部分长度为$7$）都不如假设循环节为$285714$（长度为$6$，已经开始出现的部分长度为$12$）可靠。因此她定义一个循环节的可靠程度为$a\times循环节已经开始出现的部分长度-b\times循环节长度$。请你帮她求出最可靠的循环节的可靠程度为多少。

Input

第$1$行两个正整数$a,b$，含义如题目描述。

第$2$行一个字符串$s$表示纯夏量出的小数。

$1 \le a,b \le 10^9$

$1 \le |s| \le 10^7$

Hint

样例解释

对于第1组样例：

若猜测循环节为0，则可靠度=$5 \times 1 - 3 \times 1=2$；

其中，我们把以 0 为循环节的小数也看作无限循环小数。

若猜测循环节为20，则可靠度=$5\times 2 - 3 \times 2 = 4$；

若猜测循环节为02，则可靠度=$5\times 3 - 3\times 2=9$；

若猜测循环节为020，则可靠度=$5 \times 3 - 3 \times 3=6$；

若猜测循环节为1020，则可靠度=$5\times 4 - 3 \times 4=8$。

对于第2组样例：

若猜测循环节为2，则可靠度=$2 \times 1 - 1 \times 1 = 1$；

若猜测循环节为12，则可靠度=$2 \times 4 - 1 \times 2=6$；

若猜测循环节为21，则可靠度=$2 \times 3 - 1 \times 2=4$；

若猜测循环节为212，则可靠度=$2 \times 3 - 1 \times 3=3$；

若猜测循环节为1212，则可靠度=$2 \times 4 - 1 \times 4 = 4$。

注意，计算循环节可靠度的时候不考虑整数部分。输入中给出的整数部分只是为了还原纯夏见到的数字。

Output

一个整数表示最可靠的循环节的可靠程度。

Sample Input

Sample Output

9
6

Source

642ccpcQHD

Statistic | Submit | Clarifications | Back