Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

D. Round Subset

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet's call the roundness of the number the number of zeros to which it ends.

You have an array of *n* numbers. You need to choose a subset of exactly *k* numbers so that the roundness of the product of the selected numbers will be maximum possible.

Input

The first line contains two integer numbers *n* and *k* (1 ≤ *n* ≤ 200, 1 ≤ *k* ≤ *n*).

The second line contains *n* space-separated integer numbers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{18}).

Output

Print maximal roundness of product of the chosen subset of length *k*.

Examples

Input

3 2

50 4 20

Output

3

Input

5 3

15 16 3 25 9

Output

3

Input

3 3

9 77 13

Output

0

Note

In the first example there are 3 subsets of 2 numbers. [50, 4] has product 200 with roundness 2, [4, 20] — product 80, roundness 1, [50, 20] — product 1000, roundness 3.

In the second example subset [15, 16, 25] has product 6000, roundness 3.

In the third example all subsets has product with roundness 0.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 18:37:06 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|