stamps

Problem Description

Rar the Cat has diversified his operations of being selfish. I mean, selling fish. He has now decided to sell fish online, to other felines.

As usual, being an online retailer, Rar has to mail his products to his consumers via post. This requires him to pay a certain amount of postage fees by placing stamps on them.

Rar has calculated that he needs to pay P cents to mail his products to a certain customer and there are S different types of stamps that he can purchase.

For convenience, we will call the minimum number of stamps required to pay exactly P cents as A. Given the list of all the denominations of stamps that Rar can purchase, he wants to know the value of A. Furthermore, he wants to know how many ways there are to pay exactly P cents in stamps using not more than A stamps.

For clarity, the order of using the stamps does not matter, only the composition does. For example: using 2 5cent stamps and 1 1cent stamp can be pasted as 5 + 1 + 5 or 5 + 5 + 1 or 1 + 5 + 5. However, they all have the same composition and thus is considered as a single way.

Input

The first line of input will contain 2 integers, P followed by S.

Subsequent S lines will contain 1 integer each, the denominations of the S stamps. Do note that they are not provided in any sorted order and are unique.

Output

The first line of output will be the value of A.

The second line of output should be the number of possible ways to pay exactly P cents using only A stamps.

If there are no possible way to pay exactly P cents using the stamp denominations provided, please output -1 on the first line and do not print the second line.

The number of ways to pay exactly P cents using A stamps will fit into a 32-bit signed integer.

Limits

For all testcases, the denominations of the stamps will be less than or equal to P

Subtasks

Subtask 1: Sample Testcases

Subtask 2 (21%): 0 < P ≤ 10,000 and S = 1. Furthermore, P is guaranteed to be a multiple of the only stamp denomination.

Subtask 3 (33%): 0 < P ≤ 10,000 and 0 < S ≤ 100. Furthermore, the number of ways is guaranteed to be 0 or 1.

Subtask 4 (46%): 0 < P ≤ 10,000 and 0 < S ≤ 100

Sample Input 1

50 1
10

Sample Output 1

5
1

Sample Input 2

60 3
2
20
50

Sample Output 2

3
1

Sample Input 3

60 3
5
20
50

Sample Output 3

3
2

Sample Input 4

50 1
20

Sample Output 4

-1