Non Negative Solutions To a Linear Diophantine?

I have been trying to read a lot of literature concerning the above subject but I've not found anything useful to help my case.

Suppose you're given a linear diophantine in $a_1,a_2,\ldots,a_k$ where $k\leq 10$, and we are asked to tell if $a_1 x_1 + a_2 x_2 + \cdots+a_kx_k = N$ has a non negative solution or not?

We are given many such queries, so I think regular Euclid method wouldn't be sufficient.

Also,since I anyway brought the topic, could we utilise the calculation of the Frobenius Number of the equation to answer the above query.

-