SOLVE

LATER

The Demonetization Dilemma

Problem

Editorial

Analytics

Anik is big foodie and frequently goes on outings to restaurants and food corners in the city or town he is living in. Due to the Indian government’s decision to demonetize Rs 500 and Rs 1000, Anik is in a huge scarcity for change. He cannot possibly survive without his beloved food. Notes are not available in the market, so he is having to pay only through coins. So he decides that he will pay the amount through the minimum number of coins he possibly can.

**Input:**

First line contains a number `T`

which denotes the number of test cases. Each test case contains `3`

lines.

- First line consists of a single integer
`A`

which signifies the amount Anik has to pay. - Second line consists of a single integer
`N`

which is the number of coin denominations available in the market. - Third line consists of
`N`

integers a_{1}, a_{2}, a_{3}... a_{n}denoting the coin denominations available in the market.

**Output:**

Output should consist of a positive integer which signifies the minimum number of coins in which Anik can pay. If there exists no way in which Anik can pay, print `No solution`

.

**Constraints:**

1 <= T <= 1000

0 <= A <= 10000

1 <= N <= 100

1 <= a_{i} <= 1000

Explanation

Rs 4 can be paid through 2 coins of Rs 2.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic

Initializing Code Editor...

{"0333079": "/pagelets/recommended-problems/algorithm/the-demonetization-dilemma/", "8c82902": "/pagelets/problems-hint/algorithm/the-demonetization-dilemma/", "e50a79e": "/pagelets/show-submission/algorithm/the-demonetization-dilemma/", "b80ab85": "/pagelets/suggested-problems/algorithm/the-demonetization-dilemma/", "03ea9d2": "/pagelets/problem-author-tester/algorithm/the-demonetization-dilemma/"}

realtime.hackerearth.com

80

788eae6f8c2da773578f09e1ce868317bb0eaa15

58a29e5cae2309f04b28

/realtime/pusher/auth/