The answer is $n=\left\lfloor\log _{K+1} N\right\rfloor$.
Note first that for $n \leqslant\left\lfloor\log _{K+1} N\right\rfloor$, taking $a_{i}=(K+1)^{i-1}$ works. Indeed let $r$ be maximal such that $m_{r} \neq 0$. Then on the one hand we have

$$\left|\sum_{i=1}^{n} m_{i} a_{i}\right| \leqslant \sum_{i=1}^{n} K(K+1)^{i-1}=(K+1)^{n}-1$$

So the sum is indeed not divisible by $N$.
Assume now that $n \geqslant\left\lfloor\log _{K+1} N\right\rfloor$ and look at all $n$-tuples of the form $\left(t_{1}, \ldots, t_{n}\right)$ where each $t_{i}$ is a non-negative integer with $t_{i} \leqslant K$. There are $(K+1)^{n}>N$ such tuples so there are two of them, say $\left(t_{1}, \ldots, t_{n}\right)$ and $\left(t_{1}^{\prime}, \ldots, t_{n}^{\prime}\right)$ such that

$$\sum_{i=1}^{n} t_{i} a_{i} \equiv \sum_{i=1}^{n} t_{i}^{\prime} a_{i} \bmod N$$

Now taking $m_{i}=t_{i}-t_{i}^{\prime}$ for each $i$ satisfies the requirements on the $m_{i}$ 's but $N$ divides the sum

$$\sum_{i=1}^{n} m_{i} a_{i}$$

a contradiction.