Module: The backpack problem


Problem

6 /6


Surrender - 1

Problem

The buyer wants to purchase a product worth S rubles. He has N banknotes in denominations of P1, P2, ..., PN< /code> rubles. The seller has M banknotes in denominations of Q1, Q2, ..., QM< /code>. rubles. Determine if they can pay.
 
Input: 
- the first line sets the sum S;
- in the second line - number N;
- in the third line  - N numbers P1, P2, ..., PN ;
- in the fourth line - number M;
- in the fifth line - M numbers Q1, Q2, ..., QM.
The number of banknotes from the seller and the buyer and their denominations do not exceed 100.
 
Output: if the seller can pay the buyer, print the denominations of banknotes that the buyer gives to the seller and which he receives as change. Print the number with the “+” sign if the buyer gives the banknote of the corresponding denomination to the seller and with the “-” sign if the buyer receives this banknote for change. Separate denominations of banknotes with a space.
If they can't pay, print the string Impossible.
 

 

Examples
# Input Output
1
10
3
3 9 14
2
6 2
 -2 +9 +3
2
100
3
74 35 8
2
196
 Impossible

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!