Vasya 喜欢参加 Codeforces 竞赛。当一轮结束时,Vasya 会跟踪系统测试选项卡中的所有提交内容。
有 $$$n$$$ 个解决方案,其中第 $$$i$$$ 应该在 $$$a_i$$$ 测试中进行测试,在一个测试上测试一个解决方案需要 $$$1$$$ 秒。解决方案按照从 $$$1$$$ 到 $$$n$$$ 的顺序进行判断。有 $$$k$$$ 测试流程可同时测试解决方案。他们每个人一次最多可以测试一个解决方案。
在任何时刻$$$t$$$,当某个测试过程不判断任何解决方案时,它会从队列中取出第一个解决方案,并按测试 ID 的升序在每个测试上对其进行测试。令该解决方案具有 id $$$i$$$,然后在从时间时刻 $$$t$$$ 到时间时刻 $$$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$$$ 是将每个实数映射到最接近的整数的函数。
如果在某些测试 $$$q$$$ 上测试解决方案时存在某个时间点(可能是非整数),并且标题显示“系统测试:$$$q$$$%”,则 Vasya 认为提交很有趣。找出有趣的解决方案的数量。
请注意,如果多个进程尝试同时(例如,在初始时刻)从队列中获取第一个提交,它们获取解决方案的顺序并不重要。
输入
第一行包含两个正整数$$$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$$$ 次提交的测试数量。
输出
输出唯一的整数——感兴趣的提交数量。
示例
输入 #1
2 2 49 100
输出 #1
1
输入 #2
4 2 32 100 33 1
输出 #2
2
输入 #3
14 5 48 19 6 9 50 20 3 42 38 43 36 21 44 6
输出 #3
5
注意
考虑第一个例子。在 $$$0$$$ 时刻,两个解决方案都开始测试。在 $$$49$$$ 时刻,第一个解决方案经过全面测试,因此在 $$$49.5$$$ 时刻,第二个解决方案正在测试 $$$50$$$ 上进行测试,标题显示“系统测试:$$$50$$$%”(因为两个解决方案中有一个经过充分测试)。所以,第二个解决方案很有趣。
考虑第二个例子。在 $$$0$$$ 时刻,第一个和第二个解决方案开始测试。在 $$$32$$$ 时刻,第一个解决方案已完全测试,第三个解决方案开始测试,标题为“系统测试:$$$25$$$%”。在 $$$32 + 24.5 = 56.5$$$ 时刻,第三个解决方案正在测试 $$$25$$$ 上进行测试,标题仍然相同,因此这个解决方案很有趣。之后,在时间时刻$$$32 + 33 = 65$$$对第三个解决方案进行全面测试,在时间时刻$$$65 + 1 = 66$$$对第四个解决方案进行全面测试。标题变为“系统测试:$$$75$$$%”,并且在 $$$74.5$$$ 时刻,第二个解决方案正在测试 $$$75$$$ 上进行测试。所以,这个解决方案也很有趣。总的来说,有两个有趣的解决方案。