All submissions for this problem are available.
Mr. Han has been a professional karate expert and had a long term revenge for his enemy Mr. Chao. Mr. Han had been in exile for a long time after his witful lose against Mr.Chao. Mr. Chao was an expert trainer and trained his students very well by teaching them all the good and bad actions to win a match. On the other hand, Mr. Han was not the same. He wanted his students to perform well in a match whether they lose or win.Once there was a karate competition conducted at the Mr.Han's.
Mr.Chao's team were the guests.The two teams consisted of N fighters participating in the faceoff.As the coach of home team, Mr.Han has to assign all fighters to N fights. One contestant from each team will take part in a fight. The judges will assign point to the winner and it is assumed that the judges show no partiality. Team's final score is equivalent to the sum of points earned by the contestants. Each contestant has only a single fight.
Over the years Mr.Han has become very tactful and he has gained knowledge about the opposing team and has assigned pairs such that home team gains maximum points. But Mr.Chao was always a black personality and knows the tricks very well. He somehow wants the judges to schedule the matches.
What you need to do is to provide a schedule in the best possible way.
The first line contains the number of contestants N in each team.
The following N lines describe all possible pairings of contestants. j-th element in i-th line is of the form "A(i,j):B(i,j)" which means that home team would get A(i,j) points and guest team Bi,j points if i-th contestant from home team fights against the j-th from guest team.
1 < N <= 100 0 < A(i,j), B(i,j) < 1000
Output the number of points H scored by home team and the number of points G scored by guest team seperated by a space.
Input: 3 10:7 0:20 6:5 5:5 0:10 8:10 0:0 50:0 100:0 Output: 18 17
|Time Limit:||10.7143 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, RUBY, GO, PERL, PERL6|
Fetching successful submissions
If you are still having problems, see a sample solution here.