Encryption Validity

Given a test rate, a validity period in seconds, and a list of positive integer keys. The divisibility of a key is the number of elements in the list that are greater than 1 and divide it (duplicate elements count once per occurrence). The encryption strength is the maximum divisibility multiplied by 100000.

输入格式

The first line contains instructionCount validityPeriod n; the second line contains n values keys[i]. Based on the original constraints, this site adds n≥1; the other ranges follow the original problem: the rate and the validity period are 1..10^8, and keys are 1..10^5.

输出格式

Output two integers: whether the encryption can be broken within the validity period (1 if instructionCount×validityPeriod≥strength, otherwise 0), and the encryption strength.

样例 1

输入：

1000 10000 4
2 4 8 2

输出：

1 400000

样例 2

输入：

1 1 1
1

输出：

1 0

样例 3

输入：

100 1000 3
2 3 6

输出：

0 300000