Let us call an iteration (flip two cards, and gain score or lose life) a turn.

The state of the game can be described by the number of cards \(C (\in \{0,1\})\) already flipped within the current turn, current life \(L\), the set \(S\) of cards obtained so far, and the set \(T\) of cards revealed so far (including those obtained already). Note that for two states \((C,L,S,T)\) and \((C',L',S',T')\), if \(C=C'\) and \(L \leq L'\) and \(S \subset S'\) and \(T \subset T'\), then \((C',L',S',T')\) is a better state.

We may assume that we always obtain the cards obtainable. That is, when we choose the first card in a turn, if we already know a matching pair, then we can always take those two; also, after choosing the first card, if you already know the counterpart, we can always make a pair with the second.

Also, we may assume that we always flip an unknown card if there is no matching pair among the cards revealed. (This is because, if we choose a known card as the former pick and an unknown for the latter, swapping them does not degrade the profit, so we may always choose an unknown card as the first card; also, except when we can make a pair, it is always better to increase the number of known cards, so we may choose an unknown card as the second card, too.)

Therefore, there is an optimal strategy that does not depend on the numbers written on the cards. Thus, the answer is \(X \frac{1}{N}\sum A_i\), where \(X\) is the expected number of pairs that can be obtained by a strategy that maximizes the expected number of pairs. Now we will consider how to find \(X\).

Let \(f(L, C_0, C_1)\) be the expected number of pairs we can obtain from now on, when the current life is \(L\) and there are \(2(C_0+C_1)\) cards remaining on the table, among which we have already revealed \(C_1\) of the cards (where the numbers on them are pairwise distinct).

Then, what happens in the next turn is one of the following four:

• The counterpart of the first card is known, so pick that card as the second card.
• The counterpart of the first card is unknown, but pick that card as the second card.
• The counterpart of the first card is unknown, and pick another card whose counterpart is unknown as the second, too.
• The counterpart of the first card is unknown, but that of the second is known. If the life remains, obtain that pair in the next turn.

The probability of each case can be calculated easily, and the conditional expected value for each situation can be represented recursively using \(f\).

Throughout this recursion, \(2C_0+C_1\) decreases strictly monotonically, so \(f\) can be evaluated recursively, with the base cases \(f(0,*,*)\) and \(f(*,0,*)\).

To find \(f(L,N,0)\), we need to consider \(O(LN^2)\). Since each state has a constant number of transitions, the problem has been solved in \(O(LN^2)\) time.

Note that implementations using memorized recursions may exceed the execution time limit if the constant factor is bad. (A natural memorized recursion implemented by the Writer ran in about 1700 milliseconds on PyPy.)

Sample code (C++)