G. Juan
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Xiaochang and Xiaopeng are preparing for the postgraduate entrance exam together, sitting back-to-back in the study room day after day.

Originally, Xiaochang was better at studying than Xiaopeng, so he doesn't want Xiaopeng to surpass him. Xiaopeng is very hardworking himself, but he doesn't want Xiaochang to see him working too hard.

Specifically:

  • Xiaochang has a sequence $$$A$$$ of length $$$n$$$, where the $$$i$$$-th position ($$$0 \le i \lt n$$$) $$$A_i$$$ is either 1 or 0, representing whether he looks back to check if Xiaopeng is working hard (1) or not (0).
  • Xiaopeng has a sequence $$$B$$$ of length $$$m$$$, where the $$$j$$$-th position ($$$0 \le j \lt m$$$) $$$B_j$$$ is either 1 or 0, representing whether he is working hard (1) or playing with his phone (0) at that moment.

Over the next $$$n \times m$$$ days, at 11:00 am on the $$$k$$$-th day ($$$0 \le k \lt n \times m$$$):

  • If $$$A_{k \bmod n}=1$$$, Xiaochang will look back at Xiaopeng; otherwise, he won't.
  • If $$$B_{k \bmod m}=1$$$, Xiaopeng will be working hard at that moment; otherwise, he will be playing with his phone.

The trust level of Xiaochang towards Xiaopeng increases by 1 in the following two cases:

  1. Xiaochang looks back and sees Xiaopeng playing.
  2. Xiaochang doesn't look back, but Xiaopeng is working hard.

Given $$$n$$$, $$$m$$$, and Xiaochang's sequences, the question is: Assuming Xiaopeng constructs his sequence in the optimal way, what is the maximum trust level Xiaochang can have towards Xiaopeng after $$$n \times m$$$ days?

Input

The first line contains two positive integers $$$n$$$ and $$$m$$$, as described in the problem statement.

The second line contains a binary string of length $$$n$$$, representing Xiaochang's sequence $$$A$$$.

$$$1 \le n,m \le 10^5$$$

Output

Output a single number representing the answer.

Examples
Input
3 4
111
Output
12
Input
3 2
101
Output
4
Note

For the first sample case, Xiaopeng can set his sequence to 0000, so whenever Xiaochang looks back, Xiaopeng is playing, resulting in the answer $$$n \times m=3 \times 4=12$$$.

For the second sample case, during these 6 days, Xiaopeng's observation sequence is 101101, while Xiaochang's sequence expands to $$$B_0B_1B_0B_1B_0B_1$$$.

Each day's decisions correspond to: $$$\{1,B_0\}$$$, $$$\{0,B_1\}$$$, $$$\{1,B_0\}$$$, $$$\{1,B_1\}$$$, $$$\{0,B_0\}$$$, $$$\{1,B_1\}$$$.

It's easy to see that setting $$$B_0=B_1=0$$$ yields the maximum answer of 4.