Fundraising with Angela (Part II)
Angela's initial auction was so successful that she has decided to run a second auction. She has, once again, collected many items that she would like to auction off, with proceeds to benefit needy cats. As in the first auction, she will collect a sealed envelope from each participant, and that envelope will contain a bid for each item from that participant. However, Angela has decided to change the pricing and allocation rules for this new auction.
Angela has a soft spot for participants who bid purrfectly. She defines a purrfect number to be a positive integer that is equal to two plus the sum of its positive divisors, excluding the number itself. For example, 3 is a purrfect number: it is 2 more than the sum of its divisors, excluding itself, 1. If one or more of the participants bids a purrfect number for an item, then she will allocate that item randomly to one of the perfect bidders, and she will charge them $0.
Angela really dislikes participants who bid impurrfectly. She defines an impurrfect number to be an integer that is the product of some integer and itself. For example, 25 is an impurrfect number: it is the product of 5 and itself.
If no participants bid purrfectly, then she will allocate the item to the highest bidder. If that winner bid an impurrfect number, then she will charge that winner twice their bid. Otherwise, she will charge the winner their true bid.
You need to implement a function or method that will take as input the bids of each agent for each item, and return the total revenue that Angela will collect after running her purrfect auction.
Input / Output Format
Input
The first line in the test data file contains the number x of
test cases. After this, the x test cases are given one by one.
Each test case begins with two integers n and m:
the number of participating agents in the auction (guaranteed to be an integer
value greater than 0), and the number of items Angela is auctioning off
(guaranteed to be an integer value greater than 0). After this are
n lines, each with m values; these represent the bids
for each agent and each item (all guaranteed to be nonnegative integers), in
order. For example, if the jth entry in the
ith row is 12, then agent i bid $12 for item j.
Output
The output is a single integer representing the total revenue collected by Angela during the purrfect auction.
Example:
| Input: | Output: |
|---|---|
| 3 | |
| 3 1 1 4 2 |
8 |
| 3 3 1 2 3 2 3 1 3 1 2 |
0 |
| 2 2 10 0 10 0 |
0 |