Snorlax hates working out

All submissions for this problem are available.
The days are getting warmer, and it's about time that Snorlax starts working out. Snorlax, as lazy as he is, is least interested. However, Ash is ready with a schedule, and this time it's a little bit different. Ash gives a plan for each day, telling how many days Snorlax needs to work out in the next $K$ consecutive days. The $Nday$ workout plan, prepared by Ash, consists of $NK+1$ numbers, the $i^{th}$ of which denotes the number of days that Snorlax needs to workout in the $K$ consecutive days starting from day $i$. For example, the $5day$ schedule, with $K = 3$, saying $[2$,$1$,$2]$, means that Snorlax has to work out for $2$ days, out of the $3$ consecutive days starting from day $1$. Similarly, he needs to work out for $1$ and $2$ days out of the $3$ consecutive days starting from day $2$ and day $3$ respectively. Snorlax, unable to refuse Ash, reluctantly agrees to the plan. But he wishes to minimise the number of days he works out, out of those $N$ days. He asks for your help. ###Input:  The first line will contain $T$, the number of test cases. Then the test cases follow.  Each test case contains two lines of input.  The first line of each test case contains two spaceseparated integers, $N$ and $K$.  Following the first line are $NK+1$ integers, each in a new line, $i^{th}$ of which has a value $\geq 0$ and $\leq K$, and denotes the workout plan for the $K$ consecutive days starting from day $i$. ###Output: For each test case, output in a single line, an integer, denoting the minimum number of days that Snorlax needs to work out. Print $1$, if such a schedule cannot exist. ###Constraints  $1 \leq T \leq 15$  $1 \leq K \leq N \leq 10^6$  Sum of $N$ over all test cases $\leq 10^6$ ###Sample Input: 2 5 3 3 3 3 5 2 1 2 1 2 ###Sample Output: 5 1 ###Explanation: For the first test case, with $N = 5$ and $K = 3$, the only possibility of satisfying the given schedule is when Snorlax works out for all five days.Author:  enigma27 
Tags  enigma27 
Date Added:  4032019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions