import java.util.LinkedList; 
import java.util.List; 
/* 
 * ScoreUnion.java 
 * 
 * Created on 2006년 10월 10일 (화), 오후 6:27 
 * 
 * To change this template, choose Tools | Template Manager 
 * and open the template in the editor. 
 */ 
 
/** 
 * 
 * @author 강웅빈 
 */ 
public class ScoreUnion { 
     
    public LinkedList<Score> getUnion(final List<Score> sortedListA, final List<Score> sortedListB) { 
        final LinkedList<Score> result = new LinkedList<Score>(); 
         
         
        for(Score score: sortedListA) { 
            result.add(new Score(score.did, score.score)); 
        } 
         
        int lastAidx = 0; 
        for(int ix=0; ix<sortedListB.size(); ix++) { 
            final Score bScore = sortedListB.get(ix); 
            final int curDid = bScore.did; 
            final int curScore = bScore.score; 
            for(;lastAidx < result.size();lastAidx++) { 
                final Score aScoreObj = result.get(lastAidx); 
                final int aDid = aScoreObj.did; 
                final int aScore = aScoreObj.score; 
                if(aDid < curDid) { 
                    continue; 
                } else if(aDid == curDid) { 
                    result.get(lastAidx).score = aScore + curScore; 
                    break; 
                } else { 
                    result.add(lastAidx, bScore); 
                    break; 
                } 
            } 
        } 
         
         
        return result; 
                 
                
    } 
             
    public static void main(String args[]) { 
        LinkedList<Score> a = new LinkedList<Score>(); 
        LinkedList<Score> b = new LinkedList<Score>(); 
        a.add(new Score(1, 5)); 
        a.add(new Score(5, 8)); 
        a.add(new Score(8, 2)); 
        a.add(new Score(10, 3)); 
        a.add(new Score(15, 1)); 
        b.add(new Score(1, 2)); 
        b.add(new Score(6, 1)); 
        b.add(new Score(10, 3)); 
        b.add(new Score(18, 5)); 
        b.add(new Score(21, 7)); 
         
        ScoreUnion test = new ScoreUnion(); 
         
        List<Score> result = test.getUnion(a, b); 
        for(Score scr:  result) { 
            System.out.println("[" + scr.did + "," + scr.score + "]" ); 
        } 
    } 
} 

//class Score 
 
/* 
 * Score.java 
 * 
 * Created on 2006년 10월 10일 (화), 오후 6:26 
 * 
 * To change this template, choose Tools | Template Manager 
 * and open the template in the editor. 
 */ 
 
/** 
 * 
 * @author 강웅빈 
 */ 
public class Score { 
    public Score(int d, int s) { 
        did = d; 
        score = s; 
    } 
     
    public int did; 
    public int score; 
     
}