Project Panoptes

Project Panoptes uses low cost robotic telescopes to gather observations and look for planets outside the solar system, called exoplanets. In this problem you write a simple version of the software that picks exoplanet candidates out of those observations.

The telescope records the brightness of one star once per day. A day whose brightness drops may be a day when a planet passed in front of the star. When the drops repeat at a fixed spacing, the star becomes a candidate for having an exoplanet.

Number the observation days 1 through $n$ and let $x_i$ be the brightness on day $i$. Let $m = (x_1 + \dots + x_n) / n$ be the average of all readings. Day $i$ is dim when $x_i < 0.8m$. The comparison is strict, so a day whose brightness equals exactly 80% of the average is not dim.

An integer $k$ is a period when both of these hold.

• $k \ge p$
• There is a start day $s$ with $1 \le s \le k$ and $s + k \le n$ such that every one of $s, s+k, s+2k, \dots$ that is at most $n$ is a dim day.

The second condition means two things. A period needs at least two dim days, so $k$ never exceeds $n-1$. A subset is also not enough: if days 4, 7 and 10 are dim, then $k = 3$ with $s = 1$ still fails unless days 1 and 13 are dim as well.

Find the smallest period.

The first line contains two integers $n$ and $p$ ($2 \le n \le 1000$, $1 \le p \le n-1$), where $n$ is the number of observations and $p$ is the smallest period to consider.

Each of the next $n$ lines contains one real number $x$ ($0.0 \le x \le 100.0$), the brightness of that day. The days are given in order.

Print the smallest period that satisfies the conditions. Print -1 if no such period exists.