시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (하단 참고) 256 MB 36 14 13 39.394%

문제

Alice 와 Bob 두 해적은 최근 보물섬에서 엄청난 양의 보물을 발견했다. 총 N개의 보물 상자를 발견했는데, 공평하게 번갈아가며 보물 상자를 하나씩 골라 가지기로 하였다. 각 보물 상자의 가치는 객관적으로 정하기 어렵기 때문에 두 사람 모두 자신이 생각하는 가치가 얼마인지 적어서 서로에게 공유했다. 즉, i번째 보물 상자는 Alice에겐 A[i] 달러 만큼의 가치를 갖고 Bob에겐 B[i] 달러 만큼의 가치를 갖는다. 상자를 나누어 갖기 위해 Alice부터 시작하여 Alice와 Bob은 번갈아가며 남은 상자들 중 하나를 가져가기로 했다. 상자를 하나 가져오면 상대방의 차례가 되며, N개의 상자가 모두 주인을 찾은 후 둘은 각자 갈 길을 떠나기로 했다.

편의상 보물 상자를 모두 나눈 후 Alice가 가져간 상자의 (Alice 기준대로의) 가치의 총합을 ScoreA라 하고 Bob이 가져간 상자의 (Bob 기준대로의) 가치의 총합을 ScoreB라 하자. Alice와 Bob은 서로 약속은 지키는 의리있는 해적이지만, 욕심이 많기 때문에 Alice의 목표는 (ScoreA - ScoreB)가 최대가 되도록 상자를 선택하는 것이고 Bob의 목표는 (ScoreB - ScoreA)가 최대가 되도록 상자를 선택하는 것이다.

이 두 사람은 언제나 최선을 다해서 어떤 상자를 가져갈지 결정한다.

예를 들어 N = 3 인 경우 세 개의 보물 상자가 있으며, 각 해적이 생각하는 보물 상자의 가치는 아래와 같다.

  • 상자1: A[1] = 10, B[1] = 5
  • 상자2: A[2] = 100, B[2] = 90
  • 상자 3: A[3] = 2, B[3] = 0

이 때 Alice가 상자 2를 먼저 가져가고, 그 후 Bob이 상자 1을 가져간 후, 마지막으로 Alice가 상자 3을 가져간다면, Alice는 총 102 달러 만큼 보물을 챙기고 Bob은 총 5달러 만큼 보물을 챙기게 된다. 만약 Alice가 자신의 첫 차례에 상자 2가 아닌 다른 상자를 가져간다면 (상자 1 혹은 상자 3), Bob은 자신의 차례에 상자 2를 가져갈테니, 이 경우 Alice는 10+2 = 12 달러 그리고 Bob은  90달러 만큼의 보물을 챙기게 된다. 따라서 Alice가 최선을 다한다면 첫 차례에 반드시 보물 2를 가져가야 한다.

보물 상자의 수 N과 해적 둘이 각자 생각하는 보물 상자의 가치가 주어졌을 때, 두 사람이 최선을 다해 각자의 목표를 최대화 했을 때 (ScoreA - ScoreB) 값이 무엇인지 구하는 프로그램을 작성하시오.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스에 대해 첫 줄에 정수 N이 주어지며 이는 보물 상자의 수를 나타낸다.

다음 N줄에 걸쳐서 각 보물의 가치가 공백으로 구분되어 주어진다 (첫 수는 Alice가 생각하는 가치, 두 번째 수는 Bob이 생각하는 가치).

출력

각 테스트 케이스에 대하여 두 사람이 최선을 다해 게임을 플레이 했을 때, (ScoreA - ScoreB) 값을 구하여 출력한다.

제한

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 100,000
  • 0 ≤ A[i], B[i] ≤ 100,000

예제 입력 1

5
3
10 5
100 90
2 0
3
90 100
5 10
0 2
3
10 100
100 10
50 60
4
20 10
15 20
5 8
8 9
3
0 100
0 1000
0 10

예제 출력 1

97
80
50
5
-100

테스트 케이스 1

문제에서 다루었다.

테스트 케이스 2

예제 1에서 쓰인 세 개의 보물 상자와 같지만 두 사람이 생각하는 가치가 바뀌었다. 이 경우 Alice는 상자 1을 먼저 가져가서 90 달러를 획득하고, Bob은 상자 2를 가져가서 10달러를 획득한다. 마지막으로, Alice는 남겨진 상자 3을 가져가서 0달러를 획득하여 (ScoreA-ScoreB)는 80이 된다. 

테스트 케이스 3

이 경우, Alice 와 Bob 모두 어떤 상자를 가져가더라도 항상 같은 결과가 나온다.

테스트 케이스 4

Alice는 첫 차례에 상자 2를 가져가 15달러를 획득하고 (이 방법이 Alice에게는 최선의 방법이기에 반드시 이 상자를 가져와야 한다), Bob은 자신의 첫 차례에 상자 1을 가져가 10달러를 획득하고 (마찬가지로, Alice가 이미 상자 2를 가져간 이후에 상자 1을 고르는 것이 Bob에게는 최선이다).

Alice의 두 번째 차례에 상자 4를 가져가 8 달러를 획득한 후, 마지막으로 Bob이 상자 3을 가져가 8달러를 획득한다. ScoreA = 15+8=23, ScoreB = 10 + 8 = 18 이 되어 ScoreA-ScoreB = 5가 된다.

테스트 케이스 5

Alice는 선택에 관계없이 0달러를얻게 된다. 다만, 첫 차례에 상자 2를 가져올 경우, Bob은 다음 차례에 상자 1을 가져올 수 밖에 없고, 따라서 ScoreA - ScoreB = -100 으로 (비록 음수이긴 하지만) Alice에게는 이것이 최선의 결과가 된다.

W3sicHJvYmxlbV9pZCI6IjE5MjQxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTc0XHVjODAxXHVhY2ZjIFx1YmNmNFx1YzExZCIsImRlc2NyaXB0aW9uIjoiPHA+QWxpY2UgXHVjNjQwIEJvYiBcdWI0NTAgXHVkNTc0XHVjODAxXHVjNzQwIFx1Y2Q1Y1x1YWRmYyBcdWJjZjRcdWJiM2NcdWMxMmNcdWM1ZDBcdWMxMWMgXHVjNWM0XHVjY2FkXHViMDljIFx1YzU5MVx1Yzc1OCBcdWJjZjRcdWJiM2NcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LiBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWJjZjRcdWJiM2MgXHVjMGMxXHVjNzkwXHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjI5NFx1YjM3MCwgXHVhY2Y1XHVkM2M5XHVkNTU4XHVhYzhjIFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3MCBcdWJjZjRcdWJiM2MgXHVjMGMxXHVjNzkwXHViOTdjIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWFjZThcdWI3N2MgXHVhYzAwXHVjOWMwXHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4mbmJzcDtcdWFjMDEgXHViY2Y0XHViYjNjIFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWFjMDBcdWNlNThcdWIyOTQgXHVhYzFkXHVhZDAwXHVjODAxXHVjNzNjXHViODVjIFx1YzgxNVx1ZDU1OFx1YWUzMCBcdWM1YjRcdWI4MzVcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjQ1MCBcdWMwYWNcdWI3OGMgXHViYWE4XHViNDUwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWMwZGRcdWFjMDFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjZTU4XHVhYzAwIFx1YzViY1x1YjljOFx1Yzc3OFx1YzljMCBcdWM4MDFcdWM1YjRcdWMxMWMgXHVjMTFjXHViODVjXHVjNWQwXHVhYzhjIFx1YWNmNVx1YzcyMFx1ZDU4OFx1YjJlNC4gXHVjOTg5LCBpXHViYzg4XHVjOWY4IFx1YmNmNFx1YmIzYyBcdWMwYzFcdWM3OTBcdWIyOTQmbmJzcDtBbGljZVx1YzVkMFx1YWM5MCBBW2ldIFx1YjJlY1x1YjdlYyBcdWI5Y2NcdWQwN2NcdWM3NTggXHVhYzAwXHVjZTU4XHViOTdjIFx1YWMxNlx1YWNlMCBCb2JcdWM1ZDBcdWFjOTAgQltpXSBcdWIyZWNcdWI3ZWMgXHViOWNjXHVkMDdjXHVjNzU4IFx1YWMwMFx1Y2U1OFx1Yjk3YyBcdWFjMTZcdWIyOTRcdWIyZTQuIFx1YzBjMVx1Yzc5MFx1Yjk3YyBcdWIwOThcdWIyMDRcdWM1YjQgXHVhYzE2XHVhZTMwIFx1YzcwNFx1ZDU3NCZuYnNwO0FsaWNlXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzVlYyBBbGljZVx1YzY0MCBCb2JcdWM3NDAgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTcwIFx1YjBhOFx1Yzc0MCBcdWMwYzFcdWM3OTBcdWI0ZTQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWMwYzFcdWM3OTBcdWI5N2MgXHVkNTU4XHViMDk4IFx1YWMwMFx1YzgzOFx1YzYyNFx1YmE3NCBcdWMwYzFcdWIzMDBcdWJjMjlcdWM3NTggXHVjYzI4XHViODQwXHVhYzAwIFx1YjQxOFx1YmE3MCwgTlx1YWMxY1x1Yzc1OCBcdWMwYzFcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIFx1YzhmY1x1Yzc3OFx1Yzc0NCBcdWNjM2VcdWM3NDAgXHVkNmM0IFx1YjQ1OFx1Yzc0MCBcdWFjMDFcdWM3OTAgXHVhYzA4IFx1YWUzOFx1Yzc0NCBcdWI1YTBcdWIwOThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQzYjhcdWM3NThcdWMwYzEgXHViY2Y0XHViYjNjIFx1YzBjMVx1Yzc5MFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViMDk4XHViMjA4IFx1ZDZjNCBBbGljZVx1YWMwMCBcdWFjMDBcdWM4MzhcdWFjMDQgXHVjMGMxXHVjNzkwXHVjNzU4IChBbGljZSBcdWFlMzBcdWM5MDBcdWIzMDBcdWI4NWNcdWM3NTgpIFx1YWMwMFx1Y2U1OFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NDQgU2NvcmU8c3ViPkE8XC9zdWI+XHViNzdjIFx1ZDU1OFx1YWNlMCBCb2JcdWM3NzQgXHVhYzAwXHVjODM4XHVhYzA0IFx1YzBjMVx1Yzc5MFx1Yzc1OCAoQm9iIFx1YWUzMFx1YzkwMFx1YjMwMFx1Yjg1Y1x1Yzc1OCkgXHVhYzAwXHVjZTU4XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc0NCBTY29yZTxzdWI+QjxcL3N1Yj5cdWI3N2MgXHVkNTU4XHVjNzkwLiBBbGljZVx1YzY0MCBCb2JcdWM3NDAgXHVjMTFjXHViODVjIFx1YzU3ZFx1YzE4ZFx1Yzc0MCBcdWM5YzBcdWQwYTRcdWIyOTQgXHVjNzU4XHViOWFjXHVjNzg4XHViMjk0IFx1ZDU3NFx1YzgwMVx1Yzc3NFx1YzljMFx1YjljYywgXHVjNjk1XHVjMmVjXHVjNzc0IFx1YjljZVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgQWxpY2VcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0Jm5ic3A7KFNjb3JlPHN1Yj5BPFwvc3ViPiAtIFNjb3JlPHN1Yj5CPFwvc3ViPilcdWFjMDAgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWMwYzFcdWM3OTBcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YWNlMCBCb2JcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0Jm5ic3A7KFNjb3JlPHN1Yj5CPFwvc3ViPiAtIFNjb3JlPHN1Yj5BPFwvc3ViPilcdWFjMDAgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWMwYzFcdWM3OTBcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNWI4XHVjODFjXHViMDk4IFx1Y2Q1Y1x1YzEyMFx1Yzc0NCBcdWIyZTRcdWQ1NzRcdWMxMWMgXHVjNWI0XHViNWE0IFx1YzBjMVx1Yzc5MFx1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDhcdWM5YzAgXHVhY2IwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IE4gPSAzIFx1Yzc3OCBcdWFjYmRcdWM2YjAgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWJjZjRcdWJiM2MgXHVjMGMxXHVjNzkwXHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1ZDU3NFx1YzgwMVx1Yzc3NCBcdWMwZGRcdWFjMDFcdWQ1NThcdWIyOTQgXHViY2Y0XHViYjNjIFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWFjMDBcdWNlNThcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWMwYzFcdWM3OTAxOiBBWzFdID0mbmJzcDsxMCwmbmJzcDtCWzFdID0gNTxcL2xpPlxyXG5cdDxsaT5cdWMwYzFcdWM3OTAyOiZuYnNwO0FbMl0gPSAxMDAsJm5ic3A7QlsyXSA9IDkwPFwvbGk+XHJcblx0PGxpPlx1YzBjMVx1Yzc5MCAzOiBBWzNdID0gMiwmbmJzcDtCWzNdID0gMDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI1NGMgQWxpY2VcdWFjMDAgXHVjMGMxXHVjNzkwIDJcdWI5N2MgXHViYTNjXHVjODAwIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWNlMCwgXHVhZGY4IFx1ZDZjNCBCb2JcdWM3NzQgXHVjMGMxXHVjNzkwIDFcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzA0IFx1ZDZjNCwgXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjIEFsaWNlXHVhYzAwIFx1YzBjMVx1Yzc5MCAzXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwNFx1YjJlNFx1YmE3NCwgQWxpY2VcdWIyOTQgXHVjZDFkIDEwMiBcdWIyZWNcdWI3ZWMgXHViOWNjXHVkMDdjIFx1YmNmNFx1YmIzY1x1Yzc0NCBcdWNjNTlcdWFlMzBcdWFjZTAgQm9iXHVjNzQwIFx1Y2QxZCA1XHViMmVjXHViN2VjIFx1YjljY1x1ZDA3YyBcdWJjZjRcdWJiM2NcdWM3NDQgXHVjYzU5XHVhZTMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViOWNjXHVjNTdkJm5ic3A7QWxpY2VcdWFjMDAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Y2NhYiBcdWNjMjhcdWI4NDBcdWM1ZDAgXHVjMGMxXHVjNzkwIDJcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YjJlNFx1Yjk3OCBcdWMwYzFcdWM3OTBcdWI5N2MgXHVhYzAwXHVjODM4XHVhYzA0XHViMmU0XHViYTc0IChcdWMwYzFcdWM3OTAgMSBcdWQ2MzlcdWM3NDAgXHVjMGMxXHVjNzkwIDMpLCBCb2JcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Y2MyOFx1Yjg0MFx1YzVkMCBcdWMwYzFcdWM3OTAgMlx1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDhcdWQxNGNcdWIyYzgsIFx1Yzc3NCBcdWFjYmRcdWM2YjAmbmJzcDtBbGljZVx1YjI5NCZuYnNwOzEwKzIgPSAxMiBcdWIyZWNcdWI3ZWMgXHVhZGY4XHViOWFjXHVhY2UwIEJvYlx1Yzc0MCZuYnNwOyA5MFx1YjJlY1x1YjdlYyBcdWI5Y2NcdWQwN2NcdWM3NTggXHViY2Y0XHViYjNjXHVjNzQ0IFx1Y2M1OVx1YWUzMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyZuYnNwO0FsaWNlXHVhYzAwIFx1Y2Q1Y1x1YzEyMFx1Yzc0NCBcdWIyZTRcdWQ1NWNcdWIyZTRcdWJhNzQgXHVjY2FiIFx1Y2MyOFx1Yjg0MFx1YzVkMCBcdWJjMThcdWI0ZGNcdWMyZGMgXHViY2Y0XHViYjNjIDJcdWI5N2MgXHVhYzAwXHVjODM4XHVhYzAwXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViY2Y0XHViYjNjIFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWQ1NzRcdWM4MDEgXHViNDU4XHVjNzc0IFx1YWMwMVx1Yzc5MCBcdWMwZGRcdWFjMDFcdWQ1NThcdWIyOTQgXHViY2Y0XHViYjNjIFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWFjMDBcdWNlNThcdWFjMDAmbmJzcDtcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCZuYnNwO1x1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjZDVjXHVjMTIwXHVjNzQ0IFx1YjJlNFx1ZDU3NCBcdWFjMDFcdWM3OTBcdWM3NTggXHViYWE5XHVkNDVjXHViOTdjIFx1Y2Q1Y1x1YjMwMFx1ZDY1NCBcdWQ1ODhcdWM3NDQgXHViNTRjJm5ic3A7KFNjb3JlPHN1Yj5BPFwvc3ViPiAtIFNjb3JlPHN1Yj5CPFwvc3ViPikgXHVhYzEyXHVjNzc0IFx1YmIzNFx1YzVjN1x1Yzc3OFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCBcdWM3NzRcdWIyOTQgXHViY2Y0XHViYjNjIFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHVhYzAxIFx1YmNmNFx1YmIzY1x1Yzc1OCBcdWFjMDBcdWNlNThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgKFx1Y2NhYiBcdWMyMThcdWIyOTQgQWxpY2VcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTU4XHViMjk0IFx1YWMwMFx1Y2U1OCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgQm9iXHVjNzc0IFx1YzBkZFx1YWMwMVx1ZDU1OFx1YjI5NCBcdWFjMDBcdWNlNTgpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1Y2Q1Y1x1YzEyMFx1Yzc0NCBcdWIyZTRcdWQ1NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDUwY1x1YjgwOFx1Yzc3NCBcdWQ1ODhcdWM3NDQgXHViNTRjLCAoU2NvcmU8c3ViPkE8XC9zdWI+IC0gU2NvcmU8c3ViPkI8XC9zdWI+KSBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHVjNWVjJm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgVCAmbGU7IDEwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMTAwLDAwMDxcL2xpPlxyXG5cdDxsaT4wICZsZTsgQVtpXSwgQltpXSAmbGU7IDEwMCwwMDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IDE8XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YjJlNFx1YjhlOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCAyPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzgxYyAxXHVjNWQwXHVjMTFjIFx1YzRmMFx1Yzc3OCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YmNmNFx1YmIzYyBcdWMwYzFcdWM3OTBcdWM2NDAgXHVhYzE5XHVjOWMwXHViOWNjJm5ic3A7XHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMwZGRcdWFjMDFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjZTU4XHVhYzAwIFx1YmMxNFx1YjAwY1x1YzVjOFx1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMCBBbGljZVx1YjI5NCBcdWMwYzFcdWM3OTAgMVx1Yzc0NCBcdWJhM2NcdWM4MDAgXHVhYzAwXHVjODM4XHVhYzAwXHVjMTFjIDkwIFx1YjJlY1x1YjdlY1x1Yjk3YyBcdWQ2OGRcdWI0ZGRcdWQ1NThcdWFjZTAsIEJvYlx1Yzc0MCBcdWMwYzFcdWM3OTAgMlx1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWMxMWMgMTBcdWIyZWNcdWI3ZWNcdWI5N2MgXHVkNjhkXHViNGRkXHVkNTVjXHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMsIEFsaWNlXHViMjk0IFx1YjBhOFx1YWNhOFx1YzljNCBcdWMwYzFcdWM3OTAmbmJzcDszXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YzExYyAwXHViMmVjXHViN2VjXHViOTdjJm5ic3A7XHVkNjhkXHViNGRkXHVkNTU4XHVjNWVjIChTY29yZTxzdWI+QTxcL3N1Yj4tU2NvcmU8c3ViPkI8XC9zdWI+KVx1YjI5NCA4MFx1Yzc3NCBcdWI0MWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgMzxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVhY2JkXHVjNmIwLCBBbGljZSBcdWM2NDAgQm9iIFx1YmFhOFx1YjQ1MCBcdWM1YjRcdWI1YTQgXHVjMGMxXHVjNzkwXHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWQ1NmRcdWMwYzEgXHVhYzE5XHVjNzQwIFx1YWNiMFx1YWNmY1x1YWMwMCBcdWIwOThcdWM2MjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgNDxcL3A+XHJcblxyXG48cD5BbGljZVx1YjI5NCBcdWNjYWIgXHVjYzI4XHViODQwXHVjNWQwIFx1YzBjMVx1Yzc5MCAyXHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMCAxNVx1YjJlY1x1YjdlY1x1Yjk3YyZuYnNwO1x1ZDY4ZFx1YjRkZFx1ZDU1OFx1YWNlMCAoXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc3NCBBbGljZVx1YzVkMFx1YWM4Y1x1YjI5NCBcdWNkNWNcdWMxMjBcdWM3NTggXHViYzI5XHViYzk1XHVjNzc0XHVhZTMwXHVjNWQwIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM3NzQgXHVjMGMxXHVjNzkwXHViOTdjIFx1YWMwMFx1YzgzOFx1YzY0MFx1YzU3YyBcdWQ1NWNcdWIyZTQpLCBCb2JcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Y2NhYiBcdWNjMjhcdWI4NDBcdWM1ZDAgXHVjMGMxXHVjNzkwIDFcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzAwIDEwXHViMmVjXHViN2VjXHViOTdjIFx1ZDY4ZFx1YjRkZFx1ZDU1OFx1YWNlMCAoXHViOWM4XHVjYzJjXHVhYzAwXHVjOWMwXHViODVjLCBBbGljZVx1YWMwMCBcdWM3NzRcdWJiZjggXHVjMGMxXHVjNzkwIDJcdWI5N2MgXHVhYzAwXHVjODM4XHVhYzA0IFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWMwYzFcdWM3OTAgMVx1Yzc0NCBcdWFjZTBcdWI5NzRcdWIyOTQgXHVhYzgzXHVjNzc0Jm5ic3A7Qm9iXHVjNWQwXHVhYzhjXHViMjk0IFx1Y2Q1Y1x1YzEyMFx1Yzc3NFx1YjJlNCkuPFwvcD5cclxuXHJcbjxwPkFsaWNlXHVjNzU4IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjYzI4XHViODQwXHVjNWQwIFx1YzBjMVx1Yzc5MCA0XHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMCA4IFx1YjJlY1x1YjdlY1x1Yjk3YyBcdWQ2OGRcdWI0ZGRcdWQ1NWMgXHVkNmM0LCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgQm9iXHVjNzc0IFx1YzBjMVx1Yzc5MCAzXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwMCA4XHViMmVjXHViN2VjXHViOTdjJm5ic3A7XHVkNjhkXHViNGRkXHVkNTVjXHViMmU0LiBTY29yZTxzdWI+QTxcL3N1Yj4gPSAxNSs4PTIzLCBTY29yZTxzdWI+QjxcL3N1Yj4gPSAxMCArIDggPSAxOCBcdWM3NzQgXHViNDE4XHVjNWI0IFNjb3JlPHN1Yj5BPFwvc3ViPi1TY29yZTxzdWI+QjxcL3N1Yj4gPSA1XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCA1PFwvcD5cclxuXHJcbjxwPkFsaWNlXHViMjk0IFx1YzEyMFx1ZDBkZFx1YzVkMCBcdWFkMDBcdWFjYzRcdWM1YzZcdWM3NzQgMFx1YjJlY1x1YjdlY1x1Yjk3Y1x1YzViYlx1YWM4YyZuYnNwO1x1YjQxY1x1YjJlNC4gXHViMmU0XHViOWNjLCBcdWNjYWIgXHVjYzI4XHViODQwXHVjNWQwIFx1YzBjMVx1Yzc5MCAyXHViOTdjIFx1YWMwMFx1YzgzOFx1YzYyYyBcdWFjYmRcdWM2YjAsIEJvYlx1Yzc0MCBcdWIyZTRcdWM3NGMgXHVjYzI4XHViODQwXHVjNWQwIFx1YzBjMVx1Yzc5MCAxXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YzYyYyBcdWMyMTggXHViYzE2XHVjNWQwIFx1YzVjNlx1YWNlMCwgXHViNTMwXHViNzdjXHVjMTFjJm5ic3A7U2NvcmU8c3ViPkE8XC9zdWI+IC0gU2NvcmU8c3ViPkI8XC9zdWI+ID0gLTEwMCBcdWM3M2NcdWI4NWMgKFx1YmU0NFx1Yjg1ZCBcdWM3NGNcdWMyMThcdWM3NzRcdWFlMzQgXHVkNTU4XHVjOWMwXHViOWNjKSBBbGljZVx1YzVkMFx1YWM4Y1x1YjI5NCBcdWM3NzRcdWFjODNcdWM3NzQmbmJzcDtcdWNkNWNcdWMxMjBcdWM3NTggXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIxOTI0MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBpcmF0ZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkFsaWNlIGFuZCBCb2IgYXJlIHBpcmF0ZXMsIGFuZCB0aGV5IGhhdmUmbmJzcDtkaXNjb3ZlcmVkIE4gdHJlYXN1cmUgYm94ZXMgaW4gYW4gaXNsYW5kLjxcL3A+XHJcblxyXG48cD5UaGV5IGRlY2lkZWQgdG8gc3BsaXQgdGhlIGJveGVzIGJ5IHRha2luZyB0dXJucyBhbmQgY2xhaW1pbmcgb25lIHRyZWFzdXJlIGJveCBhdCBhIHRpbWUuPFwvcD5cclxuXHJcbjxwPkl0JiMzOTtzIGRpZmZpY3VsdCB0byBtZWFzdXJlIHRoZSB2YWx1ZSBvZiBlYWNoIHRyZWFzdXJlIGJveCwgc28gQWxpY2UgYW5kIEJvYiB3b3VsZCB3cml0ZSBkb3duIHRoZWlyIHJlc3BlY3RpdmUgdmFsdWF0aW9ucyBvZiBlYWNoIG9mIHRoZSBib3hlcywgYW5kIHNoYXJlIHRoZSBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5JbiBvdGhlciB3b3JkcywgdGhlIGktdGggdHJlYXN1cmUgYm94IGlzIHdvcnRoIEFbaV0gZG9sbGFycyBmb3IgQWxpY2UgYW5kIHdvcnRoIEJbaV0gZG9sbGFycyBmb3IgQm9iLjxcL3A+XHJcblxyXG48cD5UbyBzcGxpdCBOIHRyZWFzdXJlIGJveGVzLCBBbGljZSB3b3VsZCBnbyBmaXJzdCBhbmQgdGFrZSBvbmUgb2YgdGhlICh1bmNsYWltZWQpIHRyZWFzdXJlIGJveGVzLiBUaGVuLCBCb2Igd291bGQgdGFrZSZuYnNwO29uZSwgYW5kIHNvIG9uIHVudGlsIGFsbCBib3hlcyBoYXZlIGJlZW4gY2xhaW1lZC48XC9wPlxyXG5cclxuPHA+TGV0IFNjb3JlPHN1Yj5BIDxcL3N1Yj4oU2NvcmU8c3ViPkI8XC9zdWI+KSBiZSB0aGUgc3VtIG9mIHRoZSB2YWx1ZXMgb2YgdGhlIHRyZWFzdXJlIGJveGVzIHRoYXQgQWxpY2UgKEJvYikgY2xhaW1lZCBhY2NvcmRpbmcgdG8gaGVyIChoaXMpIHZhbHVhdGlvbiwgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5BbGljZSB3YW50cyB0byBtYXhpbWl6ZSAoU2NvcmU8c3ViPkE8XC9zdWI+IC0gU2NvcmU8c3ViPkI8XC9zdWI+KSBhbmQgQm9iIHdhbnRzIHRvIG1heGltaXplIChTY29yZTxzdWI+QjxcL3N1Yj4gLSBTY29yZTxzdWI+QTxcL3N1Yj4pIGJlY2F1c2UgdGhleSBib3RoIHdhbnQgdG8gJnF1b3Q7d2luJnF1b3Q7IG92ZXIgdGhlIG90aGVyIHBlcnNvbi48XC9wPlxyXG5cclxuPHA+TGV0JiMzOTtzIGFzc3VtZSB0aGF0IGJvdGggcGlyYXRlcyB3b3VsZCBjaG9vc2UmbmJzcDt0cmVhc3VyZSBib3hlcywgb3B0aW1hbGx5LjxcL3A+XHJcblxyXG48cD5Gb3IgaW5zdGFuY2UsIHN1cHBvc2UgdGhhdCBOID0gMyBhbmQgdGhlIGZvbGxvd2luZyBhcmUgdmFsdWF0aW9ucyBvZiB0aGUgYm94ZXMgYWNjb3JkaW5nIHRvIEFsaWNlIGFuZCBCb2IuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VHJlYXN1cmUgQm94IDE6IEFbMV0gPSZuYnNwOzEwLCZuYnNwO0JbMV0gPSA1PFwvbGk+XHJcblx0PGxpPlRyZWFzdXJlIEJveCAyOiZuYnNwO0FbMl0gPSAxMDAsJm5ic3A7QlsyXSA9IDkwPFwvbGk+XHJcblx0PGxpPlRyZWFzdXJlIEJveCZuYnNwOzM6IEFbM10gPSAyLCZuYnNwO0JbM10gPSAwPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SWYgQWxpY2UgdGFrZXMgQm94IDIgZmlyc3QsIGZvbGxvd2VkIGJ5IEJvYiYjMzk7cyBjaG9pY2Ugb2YgQm94IDEsIGZvbGxvd2VkIGJ5IEFsaWNlIHRha2luZyBCb3ggMywgdGhlbiZuYnNwO1Njb3JlPHN1Yj5BPFwvc3ViPiB3b3VsZCBiZSAxMDIgKGRvbGxhcnMpIGFuZCBTY29yZTxzdWI+QjxcL3N1Yj4mbmJzcDt3b3VsZCBiZSA1IChkb2xsYXJzKS48YnIgXC8+XHJcbklmIEFsaWNlIHRha2VzIGEgZGlmZmVyZW50IGJveCB0aGFuIEJveCAyIGluIGhlciBmaXJzdCB0dXJuLCB0aGVuIEJvYiB3b3VsZCB0YWtlIEJveCAyIGluIGhpcyB0dXJuLCB3aGljaCB3b3VsZCByZXN1bHQgaW4gU2NvcmU8c3ViPkEmbmJzcDs8XC9zdWI+PSAxMiBhbmQmbmJzcDtTY29yZTxzdWI+QjxcL3N1Yj4gPSA5MC4mbmJzcDs8YnIgXC8+XHJcbkhlbmNlLCBpZiBBbGljZSBwbGF5cyBvcHRpbWFsbHksIHNoZSBtdXN0IHRha2UgQm94IDIgaW4gaGVyIHZleSBmaXJzdCB0dXJuLjxcL3A+XHJcblxyXG48cD5HaXZlbiBOIGFuZCB0aGUgdmFsdWF0aW9ucyBvZiB0aGUgYm94ZXMgZnJvbSB0aGUgdHdvIHBpcmF0ZXMsIGNvbXB1dGUgdGhlIHZhbHVlIG9mIChTY29yZTxzdWI+QTxcL3N1Yj4tU2NvcmU8c3ViPkI8XC9zdWI+KSBwcm92aWRlZCB0aGF0IGJvdGggcGlyYXRlcyB3b3VsZCBwbGF5IG9wdGltYWxseS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIFQuPFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIHRoZSBudW1iZXIgb2YgdHJlYXN1cmUgYm94ZXMsIE4uPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyB3aWxsIGNvbnRhaW4gdHdvIGludGVnZXJzLCBjb3JyZXNwb25kaW5nIHRvIHRoZSB2YWx1YXRpb25zIG9mIGEgdHJlYXN1cmUgYm94IChBbGljZSYjMzk7cyBmaXJzdCBmb2xsb3dlZCBieSBCb2ImIzM5O3MpLCBzZXBhcmF0ZWQgYnkgYSB3aGl0ZXNwYWNlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgeW91ciBwcm9ncmFtIG11c3Qgb3V0cHV0IHRoZSB2YWx1ZSBvZiZuYnNwOyhTY29yZTxzdWI+QTxcL3N1Yj4gLSBTY29yZTxzdWI+QjxcL3N1Yj4pIHByb3ZpZGVkIHRoYXQgYm90aCBwbGF5IG9wdGltYWxseS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBUICZsZTsgMTA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAxMDAsMDAwPFwvbGk+XHJcblx0PGxpPjAgJmxlOyBBW2ldLCBCW2ldICZsZTsgMTAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPkNhc2UgMTxcL3A+XHJcblxyXG48cD5UaGlzIGNhc2Ugd2FzIGRlc2NyaWJlZCBpbiB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQuPFwvcD5cclxuXHJcbjxwPkNhc2UgMjxcL3A+XHJcblxyXG48cD5BbGljZSBhbmQgQm9iJiMzOTtzIHZhbHVhdGlvbnMgYXJlIGZsaXBwZWQsIHdoZW4gY29tcGFyZWQgdG8gQ2FzZSAxLiBJbiB0aGlzIGNhc2UsIEFsaWNlIHNob3VsZCB0YWtlIEJveCAxICh3b3J0aCA5MCBkb2xsYXJzKSwgYW5kIEJvYiB3b3VsZCB0aGVuIHRha2UgQm94IDIgKHdvcnRoIDEwIGRvbGxhcnMpLiBMYXN0bHksIEFsaWNlIHdvdWxkIHRha2UgQm94IDMsIGFuZCZuYnNwOyhTY29yZTxzdWI+QTxcL3N1Yj4tU2NvcmU8c3ViPkI8XC9zdWI+KSA9IDgwIHdvdWxkIGJlIHRoZSBmaW5hbCByZXN1bHQuPFwvcD5cclxuXHJcbjxwPkNhc2UgMzxcL3A+XHJcblxyXG48cD5JbiB0aGlzIGNhc2UsIHJlZ2FyZGxlc3Mgb2Ygd2hpY2ggYm94Jm5ic3A7QWxpY2Ugb3IgQm9iIGNob29zZXMgaW4gZWFjaCB0dXJuLCB0aGUgcmVzdWx0IHdpbGwgYmUgdGhlIHNhbWUuPFwvcD5cclxuXHJcbjxwPkNhc2UgNDxcL3A+XHJcblxyXG48cD5BbGljZSB3b3VsZCB0YWtlIEJveCAyIGluIGhlciBmaXJzdCB0dXJuICh3aGljaCBpcyB0aGUgb3B0aW1hbCBjaG9pY2UgZm9yIEFsaWNlKSwmbmJzcDthbmQgQm9iIHdvdWxkIHRha2UgQm94IDEgaW4gaGlzIGZpcnN0IHR1cm4gKGxpa2V3aXNlLCB0aGlzIGlzIHRoZSBvcHRpbWFsIGNob2ljZSBmb3IgQm9iKSwmbmJzcDthbmQgQWxpY2Ugd291bGQgdGFrZSBCb3ggNCBpbiBoZXIgc2Vjb25kIHR1cm4gZm9sbG93ZWQgYnkgQm94IDMgZm9yIEJvYiYjMzk7cyBsYXN0IHR1cm4uIFRoZXJlZm9yZSwgd2UgaGF2ZSBTY29yZTxzdWI+QTxcL3N1Yj4gPSAxNSs4PTIzLCBTY29yZTxzdWI+QjxcL3N1Yj4gPSAxMCArIDggPSAxOCwgd2hpY2ggbGVhZHMgdG8mbmJzcDsgU2NvcmU8c3ViPkE8XC9zdWI+LVNjb3JlPHN1Yj5CPFwvc3ViPiA9IDUuPFwvcD5cclxuXHJcbjxwPkNhc2UgNTxcL3A+XHJcblxyXG48cD5BbGljZSB3aWxsIGFsd2F5cyBlbmQgdXAgd2l0aCBib3hlcyB0aGF0IGFyZSB3b3J0aCAwIGRvbGxhcnMuIFlldCwgaWYgQWxpY2UgdGFrZXMgQm94IDIgaW4gaGVyIGZpcnN0IHR1cm4sIHRoZW4gQm9iIGNhbiBvbmx5IHRha2UgQm94IDEgaW4gaGlzIGZpcnN0IHR1cm4sJm5ic3A7IHdoaWNoIGxlYWRzIHRvIFNjb3JlPHN1Yj5BPFwvc3ViPiAtIFNjb3JlPHN1Yj5CPFwvc3ViPiA9IC0xMDAgdGhhdCBpcyBvcHRpbWFsIGZvciBBbGljZSAoZXZlbiB0aG91Z2ggaXQmIzM5O3MgYSBuZWdhdGl2ZSBudW1iZXIpLjxcL3A+XHJcbiJ9XQ==

시간 제한

  • Java 8: 3 초
  • Python 3: 2.5 초
  • PyPy3: 2.5 초
  • Java 8 (OpenJDK): 3 초
  • Java 11: 3 초
  • Python 2: 2.5 초
  • PyPy2: 2.5 초
  • Kotlin (JVM): 3 초
  • Java 15: 3 초