ZOJ Problem Set - 2926
As we all know, TCO (TopCoder Open) Algorithm competition Round 2 will be hold on February 24. It is fortunate that many ACMers from ZJU have advanced into this round. Many coders from other countries and other universities compete in this round too.
Within 3 hours before the round, coders should register in the Arena (where coders compete), otherwise they will lose the chance to compete in this round. 5 minutes before the match begins, the register phase ends, and each coder will be assigned to a room. To make the problem easier, we simplify this phase as follow:
TC first decides how many room is needed for the match. If there are k coders that register, the number of rooms r will be the minimum integer that is greater than or equal to k / 25 (which makes each room almost 25 coders). All the rooms are marked as room0 ~ roomr-1. TC then sort all the coders by their rating (Each coder has a rating which is gained in past TopCoder matches) in descending order. The coders are marked as coder0 ~ coderk-1. Then coder i will be assigned to room i%r.
Brother Can, the coach of ZJU ACM team, makes a decision that all the ZJU competitors should be in the same room and no other coders should be in that room! He will choose some of the ZJU advancers to register for the round (Sorry to others!). But, it will still be a miracle for all the coders from ZJU to be assigned to the same room and dominate it. So, Brother Can, also known as a famous hacker, has successfully break into the TopCoder Member Infomation System, and can modify the rating of coders. Because password is needed to modify members' infomation, Brother Can can only modify ZJU members' rating. When one's rating is changed from p to q, there is |p - q| rating change. Brother Can want to make total rating change minimum.
PS: After the modification, there should not be any two coders with the same rating (otherwise the sort phase will fail).
There are multiple test cases. There are three lines for each case. The first line is two integers n (0 < n <= 1000) and m (m >= 0). n is the number of advancer from ZJU, m is the number of advancer from other countries and universities. The second line will be n non-negative intergers, the rating of n ZJU advancers. The third line will be m non-negative intergers, the rating of m other advancers. To make the sort phase simpler, all the n + m rating will be even number and distinct, and all the ratings will be lower than 10000.
Process to the end of file.
For each case, if there is a way to achieve Brother Can's goal (choose some advancers to register, modify some of their ratings, and all ZJU competitors should be in the same room and dominate it), output one interger in a line, the minimum total rating change Brother Can will make. If there is no way to do this, output "Impossible" in a line.
Author: HANG, Hang
Source: ZOJ Monthly, February 2008