Problem A Card Trading <Hide Anthony and Cora are playing Dominion, their favorite card game. In Dominion, there are T different card types, and each player has a set of cards (known as a deck). A deck D is said to have C combos if C' is the largest integer such that for C different card types in the game, D contains at least two cards of that type. Anthony currently has N cards and he wants to trade cards with Cora such that he'll have a deck with exactly K combos. For each card type i (1 ≤ i ≤ T), Anthony can choose to perform at most one transaction. There are two types of transaction: 1. Buy up to two cards of ith type from Cora at a; coins each 2. Sell all his cards of ith type for b; coins each Anthony wants to maximize his profit while obtaining a complete deck. Anthony is willing to spend coins in order to obtain a complete deck if necessary, but of course he wants to minimize his spending in that case. Note that he doesn't care about keeping the rest of his cards which don't contribute to the complete deck. Anthony has hired you to help him calculate how much money he can make if he chooses the optimal strategy for obtaining enough combos. If he has to spend money, output a negative number. Input The first line of the input contains three integers N, T, and K, 1≤K≤T≤ 100 000, 1 ≤ N≤ 2T. The next line is a list of N integers representing the cards in Anthony's deck. Each integer on this line is between 1 and T inclusive. It is guaranteed no integers appear more than twice. Finally, each of the next T lines of the input contains two integers each. The th line contains a; and bį, 1 ≤ ai, bị ≤ 10%, corresponding to the price of buying and
The next line is a list of N integers representing the cards in Anthony's deck. Each integer on this line is between 1 and T'inclusive. It is guaranteed no integers appear more than twice. Finally, each of the next T lines of the input contains two integers each. The th line contains a, and bį, 1 ≤ ai, bi ≤ 10º, corresponding to the price of buying and selling a card of type i. Output Output a single integer denoting Anthony's profit assuming he trades optimally. Explanation of Sample Input In the first example, Anthony should sell two of card 1 and buy one of card 2 and one of card 3 for a net profit of 10 coins. If he chooses to sell one of card 3 and buy one of card 2, then he'll end up spending 20 coins. Sample Input 1 Sample Output 1 432 1 3 2 1 1 50 50 20 40 30 Sample Input 2 432 1 3 2 1 1 20 50 20 40 30 10 Sample Output 2 -20 &
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!