Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/27/2022 05:59:16 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|