1121_C. System Testing_10179
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⋅m/n\right),$$$

where round(x) = ⌊{x + 0.5}⌋ 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.

Input

The first line contains two positive integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 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, …, a_n (1 ≤ a_i ≤ 150), where a_i is equal to the number of tests the i-th submission is to be run on.

Output

Output the only integer — the number of interesting submissions.

Examples

Input


2 2
49 100


Output


1


Input


4 2
32 100 33 1


Output


2


Input


14 5
48 19 6 9 50 20 3 42 38 43 36 21 44 6


Output


5

Note

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.
import java.io.*;
import java.util.ArrayDeque;

public class P543C
{
	private static int n, k, totalProgress, doneSubmissions, timer;
	private static int[] a;
	private static ArrayDeque<Submission> submissionList, submissionQueue;
	private static Process[] processList;
	
	private static class Submission
	{
		private int testNumber;
		private boolean interesting;
		
		private Submission(int testNumber)
		{
			this.testNumber = testNumber;
			this.interesting = false;
		}
	}
	
	private static class Process
	{
		private final int length;
		private final Submission submission;
		private int progress;

		private Process(Submission submission)
		{
			this.submission = submission;
			this.length = submission.testNumber;
			this.progress = 0;
		}
		
	}
	
	private static void updateProgresses()
	{
		for (int i = 0; i < k; i++)
		{
			if (processList[i] != null)
			{
				processList[i].progress++;
			}
		}
	}
	
	private static void updateProcesses()
	{
		for (int i = 0; i < k; i++)
		{
			if (processList[i] == null)
			{
				if (submissionQueue.size() != 0)
				{
					processList[i] = new Process(submissionQueue.poll());
				}
			}
			else if (processList[i].progress == processList[i].length)
			{
				doneSubmissions++;
				totalProgress = (int) (100.0 * doneSubmissions / n + 0.5);
				if (submissionQueue.size() != 0)
				{
					processList[i] = new Process(submissionQueue.poll());
				}
				else
				{
					processList[i] = null;
				}
			}
		}
	}
	
	private static void checkInteresting()
	{
		for (int i = 0; i < k; i++)
		{
			if (processList[i] != null && processList[i].progress == totalProgress)
			{
				processList[i].submission.interesting = true;
			}
		}
	}
	
	public static void main(String[] args) throws IOException, NumberFormatException
	{
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		String inputLine = input.readLine();
		String[] tokens = inputLine.split(" ");
		n = Integer.parseInt(tokens[0]);
		k = Integer.parseInt(tokens[1]);
		a = new int[n];
		submissionList = new ArrayDeque<Submission>(n);
		submissionQueue = new ArrayDeque<Submission>(n);
		processList = new Process[k];
		inputLine = input.readLine();
		tokens = inputLine.split(" ");
		for (int i = 0; i < n; i++)
		{
			a[i] = Integer.parseInt(tokens[i]);
			Submission current = new Submission(a[i]);
			submissionList.offer(current);
			submissionQueue.offer(current);
		}
		doneSubmissions = 0;
		timer = 0;
		updateProcesses();
		while (true)
		{
			timer++;
			updateProgresses();
			checkInteresting();
			updateProcesses();
			if (doneSubmissions == n)
			{
				break;
			}
		}
		int count = 0;
		for (Submission s : submissionList)
		{
			if (s.interesting)
			{
				count++;
			}
		}
		System.out.println(count);
	}
}
14 5
48 19 6 9 50 20 3 42 38 43 36 21 44 6
 2 2
49 100
 4 2
32 100 33 1
 1 100
79
 50 3
33 7 96 30 68 37 44 50 100 71 12 100 72 43 17 75 59 96 16 34 25 3 90 45 7 55 92 59 30 25 96 23 40 41 95 99 93 79 89 11 76 60 4 100 75 14 37 39 87 47
 100 10
3 114 77 78 105 87 6 122 141 100 75 118 64 18 88 37 109 72 31 101 36 10 62 18 52 17 149 115 22 150 138 48 46 42 104 8 63 21 117 58 87 80 7 131 125 118 67 13 144 43 59 67 74 13 124 77 86 148 107 11 51 9 87 52 147 22 7 22 143 12 121 123 17 35 33 87 91 140 92 38 106 10 66 26 40 100 121 42 134 127 116 111 52 139 88 30 28 106 49 19
 44 4
58 39 131 78 129 35 93 61 123 25 40 9 50 9 93 66 99 115 28 45 32 31 137 114 140 85 138 12 98 53 75 29 15 17 74 87 36 62 43 132 37 103 116 142
 18 6
22 8 11 27 37 19 18 49 47 18 15 25 8 3 5 11 32 47
 111 11
20 83 25 94 8 2 29 54 36 74 63 85 27 40 84 3 86 83 18 88 92 82 87 38 47 54 14 37 46 51 61 24 17 19 81 50 24 75 97 65 59 100 7 42 83 79 57 19 24 66 57 63 73 5 30 38 60 53 1 99 99 40 41 64 12 39 75 69 70 79 79 73 93 46 69 32 58 31 60 11 32 24 11 11 8 35 3 46 35 17 42 72 7 22 67 84 41 52 96 89 46 36 95 69 1 79 97 81 47 91 90
 50 5
1 2 4 6 8 9 10 11 14 16 19 20 23 24 26 29 30 33 36 38 41 44 45 46 48 51 53 56 59 61 62 64 65 66 68 70 72 73 76 79 80 83 86 87 90 93 96 97 98 101
 30 4
4 6 10 15 20 22 27 29 30 31 34 38 39 42 47 50 54 58 62 63 65 66 68 73 74 79 83 86 91 95
 5 2
3 13 33 45 53
 10 2
69 4 43 36 33 27 59 5 86 55
 11 4
28 31 12 19 3 26 15 25 47 19 6
 100 100
1 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
 100 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
 19 3
43 47 64 91 51 88 22 66 48 48 92 91 16 1 2 38 38 91 91
 10 3
12 21 26 32 40 51 56 57 67 75
 2 2
50 100
 50 3
33 7 96 30 68 37 44 50 100 71 12 100 72 43 17 75 59 96 16 34 25 3 90 45 7 55 92 59 30 25 96 23 40 41 95 99 93 97 89 11 76 60 4 100 75 14 37 39 87 47
 100 10
3 114 77 78 105 87 6 122 141 100 75 118 64 18 88 37 109 72 31 101 36 10 62 18 52 17 149 115 22 150 138 48 46 42 104 8 63 21 117 58 87 80 7 131 125 118 67 13 144 43 59 67 74 13 124 77 86 148 107 11 51 9 87 52 147 22 7 22 143 12 121 123 17 35 33 87 91 140 92 38 106 10 54 26 40 100 121 42 134 127 116 111 52 139 88 30 28 106 49 19
 18 6
22 8 11 27 37 13 18 49 47 18 15 25 8 3 5 11 32 47
 111 11
20 83 25 94 8 2 29 54 36 74 63 85 27 40 84 3 23 83 18 88 92 82 87 38 47 54 14 37 46 51 61 24 17 19 81 50 24 75 97 65 59 100 7 42 83 79 57 19 24 66 57 63 73 5 30 38 60 53 1 99 99 40 41 64 12 39 75 69 70 79 79 73 93 46 69 32 58 31 60 11 32 24 11 11 8 35 3 46 35 17 42 72 7 22 67 84 41 52 96 89 46 36 95 69 1 79 97 81 47 91 90
 30 4
4 6 10 15 39 22 27 29 30 31 34 38 39 42 47 50 54 58 62 63 65 66 68 73 74 79 83 86 91 95
 5 2
3 13 33 45 27
 10 2
114 4 43 36 33 27 59 5 86 55
 100 100
1 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 18 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
 100 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 132 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
 19 6
43 47 64 91 51 88 22 66 48 48 92 91 16 1 2 38 38 91 91
 4 1
32 100 33 1
 100 10
3 114 77 78 105 87 6 122 141 100 75 118 64 18 88 37 109 72 31 101 36 10 62 18 52 17 149 115 22 150 138 48 46 42 104 8 63 21 117 58 87 80 7 131 125 118 67 13 144 43 59 67 74 13 124 77 86 148 107 11 51 9 87 52 147 22 7 22 143 12 121 123 17 35 33 12 91 140 92 38 106 10 54 26 40 100 121 42 134 127 116 111 52 139 88 30 28 106 49 19
 100 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 132 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
 19 6
43 47 64 91 51 88 22 66 48 48 92 45 16 1 2 38 38 91 91
 111 11
20 83 25 94 8 2 29 54 33 74 63 85 27 40 84 3 23 83 18 88 92 82 87 38 47 54 14 37 15 51 61 24 17 19 81 50 24 75 97 65 59 100 7 42 83 79 57 19 24 66 57 63 73 5 30 38 60 53 1 99 99 40 41 64 12 39 75 69 70 79 79 73 93 46 69 32 58 31 60 11 32 24 11 11 8 35 3 46 35 17 42 72 7 22 67 84 41 52 96 89 46 36 95 69 1 79 97 81 47 91 90
 100 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 132 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 64 100
 44 4
58 39 131 78 129 35 93 61 123 25 40 9 50 9 93 66 99 115 28 45 32 31 137 114 140 85 3 12 98 53 75 29 15 17 74 87 36 62 43 132 37 103 116 142
 11 4
28 31 12 19 3 1 15 25 47 19 6
 10 3
12 21 4 32 40 51 56 57 67 75
 14 5
48 19 6 9 50 20 3 42 38 43 9 21 44 6
 50 3
33 7 96 30 68 37 44 50 100 71 12 100 72 43 17 75 59 96 16 34 25 3 90 45 7 55 92 59 30 25 96 23 40 41 95 99 93 97 89 11 76 76 4 100 75 14 37 39 87 47
 44 4
58 39 131 78 129 35 93 61 123 25 40 9 50 9 93 66 99 115 28 45 32 31 137 114 140 101 3 12 98 53 75 29 15 17 74 87 36 62 43 132 37 103 116 142
 18 6
22 8 11 27 37 13 18 49 47 18 15 25 7 3 5 11 32 47
 111 11
20 83 25 94 8 2 29 54 33 74 63 85 27 40 84 3 23 83 18 88 92 82 87 38 47 54 14 37 46 51 61 24 17 19 81 50 24 75 97 65 59 100 7 42 83 79 57 19 24 66 57 63 73 5 30 38 60 53 1 99 99 40 41 64 12 39 75 69 70 79 79 73 93 46 69 32 58 31 60 11 32 24 11 11 8 35 3 46 35 17 42 72 7 22 67 84 41 52 96 89 46 36 95 69 1 79 97 81 47 91 90
 30 4
4 6 10 15 39 22 27 29 30 31 34 38 39 42 47 50 54 58 62 63 65 66 68 73 74 79 83 86 26 95
 5 2
6 13 33 45 27
 10 2
125 4 43 36 33 27 59 5 86 55
 100 100
1 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 18 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 6 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
 10 3
12 21 4 32 40 51 103 57 67 75
 14 5
48 19 6 9 50 20 3 42 38 43 9 21 44 11
 50 3
33 7 96 30 68 37 44 50 100 71 12 100 72 43 17 75 59 96 16 34 25 1 90 45 7 55 92 59 30 25 96 23 40 41 95 99 93 97 89 11 76 76 4 100 75 14 37 39 87 47
 100 10
3 114 77 78 105 87 6 122 141 100 75 118 64 18 88 37 109 72 31 101 36 10 62 18 52 17 149 115 22 150 138 48 46 42 104 8 63 21 117 58 87 80 7 131 125 118 67 13 144 43 59 67 74 13 124 77 86 148 107 22 51 9 87 52 147 22 7 22 143 12 121 123 17 35 33 12 91 140 92 38 106 10 54 26 40 100 121 42 134 127 116 111 52 139 88 30 28 106 49 19
 44 4
58 39 131 78 129 68 93 61 123 25 40 9 50 9 93 66 99 115 28 45 32 31 137 114 140 101 3 12 98 53 75 29 15 17 74 87 36 62 43 132 37 103 116 142
 18 6
22 8 11 27 37 13 18 49 47 18 15 25 1 3 5 11 32 47
 30 4
4 6 10 15 39 22 27 29 30 31 34 38 39 42 47 50 56 58 62 63 65 66 68 73 74 79 83 86 26 95
 5 2
6 10 33 45 27
 10 2
125 4 43 36 33 27 59 1 86 55
 100 100
1 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 18 26 27 28 29 30 8 32 33 34 35 36 37 38 39 40 41 42 43 44 6 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
 19 6
43 47 63 91 51 88 22 66 48 48 92 45 16 1 2 38 38 91 91
 10 3
12 21 1 32 40 51 103 57 67 75
 14 5
48 19 6 9 50 20 3 42 38 43 9 20 44 11
 50 3
33 7 96 30 68 37 44 50 100 71 12 100 72 43 17 75 59 96 16 34 25 1 90 45 7 55 92 59 30 25 96 23 40 41 95 99 93 97 89 11 76 76 4 101 75 14 37 39 87 47
 44 4
58 39 131 78 129 68 93 61 137 25 40 9 50 9 93 66 99 115 28 45 32 31 137 114 140 101 3 12 98 53 75 29 15 17 74 87 36 62 43 132 37 103 116 142
 18 6
22 8 11 27 37 5 18 49 47 18 15 25 1 3 5 11 32 47
 111 11
20 83 25 94 8 2 29 54 33 74 63 85 27 40 84 2 23 83 18 88 92 82 87 38 47 54 14 37 15 51 61 24 17 19 81 50 24 75 97 65 59 100 7 42 83 79 57 19 24 66 57 63 73 5 30 38 60 53 1 99 99 40 41 64 12 39 75 69 70 79 79 73 93 46 69 32 58 31 60 11 32 24 11 11 8 35 3 46 35 17 42 72 7 22 67 84 41 52 96 89 46 36 95 69 1 79 97 81 47 91 90
 30 4
4 6 10 15 39 22 27 29 48 31 34 38 39 42 47 50 56 58 62 63 65 66 68 73 74 79 83 86 26 95
 5 2
6 3 33 45 27
 100 100
1 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 18 26 27 28 29 30 8 32 33 34 35 36 37 38 39 40 41 42 43 44 6 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 80 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
 100 10
1 2 3 4 5 6 7 8 9 10 11 15 13 14 15 16 17 18 19 20 2 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 132 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 64 100
 19 6
43 47 63 91 51 88 22 66 48 48 92 27 16 1 2 38 38 91 91
 10 3
12 20 1 32 40 51 103 57 67 75
 14 5
48 19 6 9 50 20 3 62 38 43 9 20 44 11
 50 3
33 7 96 30 68 37 44 50 100 71 12 100 72 43 17 75 59 96 16 34 25 1 90 45 7 55 92 59 30 34 96 23 40 41 95 99 93 97 89 11 76 76 4 101 75 14 37 39 87 47
 44 4
58 39 131 78 129 68 93 61 137 25 40 9 50 9 93 66 99 115 28 45 32 31 137 114 140 101 3 12 98 53 75 29 15 21 74 87 36 62 43 132 37 103 116 142
 18 6
22 8 11 27 37 5 18 49 47 18 15 25 2 3 5 11 32 47
 111 11
20 83 25 94 8 2 3 54 33 74 63 85 27 40 84 2 23 83 18 88 92 82 87 38 47 54 14 37 15 51 61 24 17 19 81 50 24 75 97 65 59 100 7 42 83 79 57 19 24 66 57 63 73 5 30 38 60 53 1 99 99 40 41 64 12 39 75 69 70 79 79 73 93 46 69 32 58 31 60 11 32 24 11 11 8 35 3 46 35 17 42 72 7 22 67 84 41 52 96 89 46 36 95 69 1 79 97 81 47 91 90

5
 1
 2
 0
 24
 59
 25
 2
 50
 35
 16
 0
 4
 3
 98
 90
 10
 3
 0
 24
 59
 3
 48
 16
 0
 5
 98
 90
 7
 1
 58
 89
 6
 47
 88
 24
 0
 5
 5
 24
 24
 3
 48
 16
 0
 5
 98
 6
 5
 24
 58
 24
 3
 16
 0
 5
 98
 6
 6
 5
 24
 24
 6
 47
 16
 0
 98
 88
 6
 6
 5
 24
 24
 6
 47
