Let's start by solving the problem for relatively small values of ~K~ (up to a few thousand). This can be accomplished with dynamic programming. Let ~DP[k]~ be the answer for ~K = k~. That is, the maximum number of denominations no larger than ~K~ which we can use such that ~K~ is unattainable.

For a given ~k~, assuming that we'll be able to use at least ~1~ denomination, let's consider each possible value ~d~ ~(2 \le d < k)~ such that the largest denomination used will be ~d~. ~d~ must not be one of the forbidden denominations, and must not be a divisor of ~k~.

For a given ~d~, the greedy algorithm will use coins of that denomination until it's ~r = k \bmod d~ away from its target amount of money, essentially reducing us to a subproblem with ~K = r~. Along the way, we can also freely use all non-forbidden denominations between ~r+1~ and ~d~, inclusive.

Let ~F(x, y)~ be the number of non-forbidden denominations in the interval ~[x, y]~, which can be implemented in ~\mathcal O(\log N)~ time using binary search once the values ~D_{1 \dots N}~ are sorted. This brings us to the recurrence ~DP[k] = \max\{DP[k \bmod d]+F((k \bmod d)+1, d)\}~ over all valid values of ~d~.

The time complexity of the algorithm described above is ~\mathcal O(K^2 \log N)~, which is far too slow for full marks when ~K~ is as large as ~10^9~. We need to next make the insight that larger values of ~d~ (ones which are only slightly smaller than ~k~) are generally more optimal than smaller values of ~d~. This is fairly intuitive as choosing a smaller value ~D_1~ over a larger value ~D_2~ means skipping ~1~ or more valid denominations in the interval ~[D_1+1, D_2]~ which we could otherwise have used. Of course, ~DP[k \bmod D_1]~ could still turn out to be larger than ~DP[k \bmod D_2]~, so it's not always optimal to use the first valid denomination smaller than ~k~.

However, it's a fairly safe guess that the initial value of ~d~ should be no smaller than, let's say, ~K-5000~. This is convenient because, not only do we only need to try ~5000~ values of ~d~ to compute ~DP[K]~, but we only need to have computed ~DP[1 \dots 5000]~ to complement this (as ~K \bmod d~ will be at most ~5000~). We can compute that many ~DP~ values efficiently enough.

To be more precise, we can prove that we only need to consider initial values of ~d~ no smaller than ~K-N-1~ (and so, only compute ~DP[1 \dots (N+1)]~). If we find a valid value ~D_2~ such that ~K \bmod (D_2-1)~ is a non-forbidden denomination, then ~DP[K \bmod D_2]~ is as large as possible (as we'll be able to use all smaller non-forbidden denominations), meaning that it can't be more optimal to skip ~D_2~ in favour of any smaller value ~D_1~. A value of ~D_2~ meeting these criteria no smaller than ~K-N-1~ must exist (it may be as small as exactly ~K-N-1~ if all denominations in the interval ~[K-N, K-1]~ are forbidden, for example). In the end, then, we can achieve a time complexity of ~\mathcal O(N^2 \log N)~.