Thornhill Computer Club 2023 - September Contest - Problem 7

Da Perfect Burger🥰

After fountain diving (theft) for 16 years saving up all his profits, JoePeewee is ready to order a burger from Da Perfect Burger™ Restaurant.

What makes Da Perfect Burger™ burgers the greatest in the world is the customizability of their ingredients to fit your definition of perfect™. They have options that no other burger restaurants have: horse, iphone™, human, and most perplexing of all pickles™. However, due to the ingredients' exotic nature, their availability and price changes from day™ to day.

To™ get the most bang out of his buck™, JoePeewee™ is looking for a burger™ that is as close to his budget™ as possible without exceeding his budget. While he isn't picky on what is in his burger, he still wants to have mandatory™ ingredients that must be included in his burger.

Can™ you™ help find JoePeewee™ his™ perfect burger?™

Input Specification™

The first line of input contains an integer ~C~ ~(1 \le C \le 10^6)~ representing JoePeewee's budget for his perfect burger.

The second line of input contains two integers ~N~ ~(1 \le N \le 50)~ and ~M~ ~(1 \le M \le 10)~ representing the total number of ingredients and the number of mandatory ingredients respectively.

The next ~N~ lines contains integers ~N_i~ ~(1 \le N_i \le 10^9)~ representing the cost of ingredient ~i~.

The next ~M~ lines contains integers ~M_i~ ~(1 \le M_i \le n-1)~ representing the indices of the mandatory ingredients on JoePeewee's burger. Index ~i~ starts at zero.

Output Specification

Output an integer corresponding to the maximum cost of the burger that is less than or equal to the budget.

If it is impossible to purchase a burger with the mandatory ingredients without exceeding the budget, print IMPOSSIBLE.

Sample Input 1

2
1 1
1
0

Sample Output 1

2

Explanation for Sample Output 1

Here, the only available ingredient is ingredient 0, costing a total of one dollar.
This ingredient 0 also happens to be a mandatory ingredient.
After purchasing the mandatory ingredient, JoePeewee has one dollar left.
To get to as close to his budget as possible, he spend his remaining money purchasing one more instance of ingredient 0.
Purchasing a burger with two of the 0th ingredient on the list (costing 1 dollar each) would cost 2 dollars, the exact value of the budget.

Sample Input 2

13
2 1
11
2
1

Sample Output 2

13

Explanation for Sample Output 2

After purchasing mandatory ingredient 1, JoePeewee's remaining budget will be 11 dollars.
To as close to the budget as possible, JoePeewee can purchase one instance of ingredient 0, bringing his total amount spent to 13 dollars.
This is the closest value possible (while being less than or equal to) to the budget of 13.

Sample Input 3

90
4 1
91
1
1
1
0

Sample Output 3

IMPOSSIBLE

Explanation for Sample Output 3

Since the 0th ingredient is mandatory and costs 91 dollars. You would exceed the budget of 90 no matter what.