Coin Collection from Greedy Change

In a country there are \(N\) types of coins in circulation, including a 1‑cent coin. In addition, there is a paper note of \(K\) cents, whose value exceeds that of any coin. A coin collector wishes to collect one specimen of each type of coin. He already has some coins, but currently he only has a \(K\)‑cent note in his wallet. In a store, all items are sold at prices less than \(K\) cents (i.e. 1 cent, 2 cents, 3 cents, \(\cdots\), \(K-1\) cents). When the store gives change from a transaction, it follows the algorithm below:

1. Let the change amount be \(A\) cents.
2. Find the coin with the greatest denomination \(B\) such that \(B \le A\) (\(B\) is one of the circulating coin types).
3. Give the customer one \(B\)‑cent coin and subtract \(B\) from \(A\).
4. If \(A=0\), stop; otherwise, repeat from step 2.

The collector makes a purchase using his \(K\)‑cent note. During this transaction, he will receive change consisting of several coins. Some of these coins might already be in his collection. Your task is to determine:

• The maximum number of different coin types (that he does not already own) he can obtain from the change.
• Among the purchase prices that yield this maximum, what is the most expensive item the store can sell him?
• Note: The change is given using the greedy algorithm described above.

Input Format: The input consists of multiple lines. The first line contains two integers \(N\) and \(K\), where \(N\) is the number of coin denominations and \(K\) is the value of the paper note. The second line contains \(N\) distinct integers representing the coin denominations (in cents). It is guaranteed that one of the coin denominations is 1 and that every coin denomination is less than \(K\). The third line contains an integer \(M\) denoting how many types of coins the collector already owns. The fourth line contains \(M\) distinct integers representing the coin denominations already in his collection.

Output Format: Output two integers separated by a space. The first integer is the maximum number of new coin types (coins not already owned) that the collector can obtain from the change. The second integer is the maximum purchase price (in cents) among those that yield this maximum.

inputFormat

The input is given as follows:

N K
c1 c2 ... cN
M
m1 m2 ... mM

Where:

• \(N\) and \(K\) are integers with \(K\) greater than any coin denomination.
• The second line contains \(N\) distinct coin denominations in cents (including 1).
• \(M\) is an integer representing the number of coin types the collector already owns.
• The fourth line contains \(M\) distinct integers denoting the coin denominations already in his collection.

outputFormat

Output two integers: the maximum number of new coin types the collector can obtain through the transaction and the highest purchase price (in cents) that achieves this maximum, separated by a space.

sample

3 10
1 3 4
1
3

2 5