CF1121C.System Testing

Vasya likes taking part in Codeforces contests. When a round is over, Vasya follows all submissions in the system testing tab.

There are $n$ solutions, the $i$-th of them should be tested on $a_i$ tests, testing one solution on one test takes $1$ second. The solutions are judged in the order from $1$ to $n$. There are $k$ testing processes which test solutions simultaneously. Each of them can test at most one solution at a time.

At any time moment $t$ when some testing process is not judging any solution, it takes the first solution from the queue and tests it on each test in increasing order of the test ids. Let this solution have id $i$, then it is being tested on the first test from time moment $t$ till time moment $t + 1$, then on the second test till time moment $t + 2$ and so on. This solution is fully tested at time moment $t + a_i$, and after that the testing process immediately starts testing another solution.

Consider some time moment, let there be exactly $m$ fully tested solutions by this moment. There is a caption "System testing: $d$%" on the page with solutions, where $d$ is calculated as

$$d = round\\left(100\\cdot\\frac{m}{n}\\right),$$

where $round(x) = \lfloor{x + 0.5}\rfloor$ is a function which maps every real to the nearest integer.

Vasya calls a submission interesting if there is a time moment (possibly, non-integer) when the solution is being tested on some test $q$, and the caption says "System testing: $q$%". Find the number of interesting solutions.

Please note that in case when multiple processes attempt to take the first submission from the queue at the same moment (for instance, at the initial moment), the order they take the solutions does not matter.

瓦西里喜欢参加 Codeforces 的比赛。每轮比赛结束后，瓦西里都会在“系统测试”标签页中关注所有提交的评测过程。

共有 $n$ 个提交，其中第 $i$ 个提交需要在 $a_i$ 个测试点上进行评测；每个测试点的评测耗时均为 $1$ 秒。提交按编号从 $1$ 到 $n$ 的顺序依次评测。系统中共有 $k$ 个并行的评测进程，每个进程同一时刻最多只能评测一个提交。

在任意时刻 $t$，若某个评测进程当前未在评测任何提交，则它会立即从队列头部取出第一个待评测提交，并按测试点编号从小到大的顺序依次对该提交进行评测。设该提交编号为 $i$，则它在时刻 $t$ 至 $t+1$ 之间评测第一个测试点，在时刻 $t+1$ 至 $t+2$ 之间评测第二个测试点，依此类推；该提交将在时刻 $t + a_i$ 完成全部评测，此后该评测进程立即开始评测下一个提交。

考虑某一时刻，设截至该时刻恰好有 $m$ 个提交已完成全部评测。此时页面上显示的标题为“系统测试：$d$%”，其中 $d$ 按如下公式计算：

$$d = round\left(100\cdot\frac{m}{n}\right),$$

这里 $round(x) = \lfloor{x + 0.5}\rfloor$ 表示将任意实数 $x$ 四舍五入到最近的整数（当小数部分恰为 $0.5$ 时向正无穷方向取整）。

瓦西里称一个提交是有趣的，如果存在某个时刻（该时刻可以是非整数），使得该提交正在评测第 $q$ 个测试点，且此时页面标题恰好显示为“系统测试：$q$%”。请计算有趣的提交总数。

请注意：若多个评测进程在同一时刻（例如初始时刻）同时尝试从队列头部取走第一个提交，则它们取走提交的顺序无关紧要。

The first line contains two positive integers $n$ and $k$ ($1 \le n \le 1000$, $1 \le k \le 100$) standing for the number of submissions and the number of testing processes respectively.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 150$), where $a_i$ is equal to the number of tests the $i$-th submission is to be run on.

第一行包含两个正整数 $n$ 和 $k$（$1 \le n \le 1000$，$1 \le k \le 100$），分别表示提交次数和测试进程数。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 150$），其中 $a_i$ 表示第 $i$ 次提交需运行的测试用例数量。

Output the only integer — the number of interesting submissions.

输出唯一的整数——有趣提交的数量。

Consider the first example. At time moment $0$ both solutions start testing. At time moment $49$ the first solution is fully tested, so at time moment $49.5$ the second solution is being tested on the test $50$, and the caption says "System testing: $50$%" (because there is one fully tested solution out of two). So, the second solution is interesting.

Consider the second example. At time moment $0$ the first and the second solutions start testing. At time moment $32$ the first solution is fully tested, the third solution starts testing, the caption says "System testing: $25$%". At time moment $32 + 24.5 = 56.5$ the third solutions is being tested on test $25$, the caption is still the same, thus this solution is interesting. After that the third solution is fully tested at time moment $32 + 33 = 65$, the fourth solution is fully tested at time moment $65 + 1 = 66$. The captions becomes "System testing: $75$%", and at time moment $74.5$ the second solution is being tested on test $75$. So, this solution is also interesting. Overall, there are two interesting solutions.

考虑第一个例子。在时刻 $0$，两个程序同时开始系统测试。在时刻 $49$，第一个程序完成全部测试；因此在时刻 $49.5$，第二个程序正在测试第 $50$ 个测试用例，此时界面显示“系统测试：$50$%”（因为两个程序中已有一个完成全部测试）。因此，第二个程序是“有趣的”。

考虑第二个例子。在时刻 $0$，第一个和第二个程序同时开始系统测试。在时刻 $32$，第一个程序完成全部测试，第三个程序开始测试，此时界面显示“系统测试：$25$%”。在时刻 $32 + 24.5 = 56.5$，第三个程序正在测试第 $25$ 个测试用例，界面显示仍为“系统测试：$25$%”，因此该程序是“有趣的”。随后，第三个程序于时刻 $32 + 33 = 65$ 完成全部测试，第四个程序于时刻 $65 + 1 = 66$ 完成全部测试。此时界面显示变为“系统测试：$75$%”，而在时刻 $74.5$，第二个程序正在测试第 $75$ 个测试用例。因此，该程序也是“有趣的”。综上，共有两个“有趣的”程序。