시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (하단 참고) 256 MB 9 6 5 83.333%

문제

당신은 슈퍼 컴퓨터에서 총 N개의 프로그램을 순차적으로 실행하여 실험을 해야한다.

편의상 프로그램은 1번부터 N번까지 번호가 매겨져 있으며 i번 프로그램은 총 H[i]시간 동안 실행되며 이 프로그램의 희망 데드라인은 지금부터 D[i]시간 후다.

N개의 프로그램이 있으므로 실행하는 순서는 총 N! 가지가 가능하다.

i번 프로그램이 끝나는 시각을 지금부터 C[i] 시간 후 라고 하자. 편의상 max(0, C[i] - D[i]) 를 i번 프로그램의 "지각도" 라고 칭하자 (희망 데드라인보다 늦게 끝나지 않은 경우엔 지각도가 0이다).

"최대 지각도"는 N개 프로그램의 지각도 중 최대값으로 정의한다.

그런데 이 슈퍼 컴퓨터에는 특이한 기능이 있는데, N개의 프로그램 중 딱 하나의 프로그램을 (당신이) "최우선 처리 대상"으로 지정하여 해당 프로그램은 무조건 1시간만에 실행되도록 할 수 있다.

예를 들어 N = 3, H = [2, 4, 6], D = [3, 5, 8]이라 하자.

이 경우, 1번부터 3번 프로그램까지 순서대로 실행을 하고 3번 프로그램 실행시간을 1시간이 되도록 지정했다면,

1번 프로그램은 지금부터 시작하여 2시간 후에 끝나며 (C[1] = 2), 2번은 그로부터 4시간 후에 끝나고 (C[2] = 6), 3번은 그로부터 1시간 후에 끝나서 C[3] = 7이 된다.

이 때 각 프로그램의 지각도는 0, 1, 0이며, 이 중 최대값이 1이므로 최대 지각도는 1이다.

같은 예제에서 3번 프로그램부터 1번 프로그램까지 역순으로 실행하고, 3번 프로그램의 실행시간을 1시간이 되도록 지정했다면,

3번 프로그램은 지금부터 시작하여 1시간 후에 끝나며 (C[3] = 1), 2번은 그로부터 4시간 후 (C[2] = 5), 1번은 그로부터 2시간 후에 끝나서 C[1] = 7이 된다.

이 때 각 프로그램의 지각도는 4, 0, 0이며, 이 중 최대값이 4이므로 최대 지각도는 4이다.

이 예제의 경우, 첫 번째 방법이 최대 지각도를 최소화 하는 방법이다.

입력으로 N개의 프로그램의 실행시간과 희망 데드라인이 주어졌을 때, 달성 가능한 최대 지각도의 최소값을 구하시오.

입력

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

각 테스크 케이스는 세 줄에 걸쳐 주어지는데, 그 중 첫 줄에 프로그램의 수 N이 주어진다.

둘째 줄에 N개의 정수가 공백으로 구분되어 주어지며, 실행시간 H[i]를 나타낸다.

셋째 줄에 N개의 정수가 공백으로 구분되어 주어지며, 희망 데드라인 D[i]를 나타낸다.

출력

각 테스트 케이스에 대해 달성 가능한 최대 지각도의 최소값을 출력한다.

제한

  • 1 ≤ T ≤ 10
  • 2 ≤ N ≤ 100,000
  • 1 ≤ H[i], D[i] ≤ 1,000

예제 입력 1

4
3
2 4 6
3 5 8
3
4 9 1
10 9 20
3
4 3 5
2 1 3
5
8 1 2 6 2
8 9 6 2 1

예제 출력 1

1
0
5
5
W3sicHJvYmxlbV9pZCI6IjE5NTk0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjg4XHVkMzdjIFx1Y2VmNFx1ZDRlOFx1ZDEzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1YzI4OFx1ZDM3YyBcdWNlZjRcdWQ0ZThcdWQxMzBcdWM1ZDBcdWMxMWMgXHVjZDFkIE5cdWFjMWNcdWM3NTggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1YzIxY1x1Y2MyOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWMyZTRcdWQ1ODlcdWQ1NThcdWM1ZWMmbmJzcDtcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQzYjhcdWM3NThcdWMwYzEgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCBpXHViYzg4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBcdWNkMWQgSFtpXVx1YzJkY1x1YWMwNCBcdWIzZDlcdWM1NDggXHVjMmU0XHVkNTg5XHViNDE4XHViYTcwIFx1Yzc3NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHVkNzZjXHViOWRkIFx1YjM3MFx1YjRkY1x1Yjc3Y1x1Yzc3OFx1Yzc0MCBcdWM5YzBcdWFlMDhcdWJkODBcdWQxMzAgRFtpXVx1YzJkY1x1YWMwNCBcdWQ2YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyBcdWMyZTRcdWQ1ODlcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMjk0IFx1Y2QxZCBOISBcdWFjMDBcdWM5YzBcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5pXHViYzg4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWIwNWRcdWIwOThcdWIyOTQgXHVjMmRjXHVhYzAxXHVjNzQ0IFx1YzljMFx1YWUwOFx1YmQ4MFx1ZDEzMCBDW2ldIFx1YzJkY1x1YWMwNCBcdWQ2YzQgXHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4mbmJzcDtcdWQzYjhcdWM3NThcdWMwYzEgbWF4KDAsIENbaV0gLSBEW2ldKSBcdWI5N2MgaVx1YmM4OCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggJnF1b3Q7XHVjOWMwXHVhYzAxXHViM2M0JnF1b3Q7IFx1Yjc3Y1x1YWNlMCBcdWNlNmRcdWQ1NThcdWM3OTAgKFx1ZDc2Y1x1YjlkZCBcdWIzNzBcdWI0ZGNcdWI3N2NcdWM3NzhcdWJjZjRcdWIyZTQgXHViMmE2XHVhYzhjIFx1YjA1ZFx1YjA5OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQ0IFx1YzljMFx1YWMwMVx1YjNjNFx1YWMwMCAwXHVjNzc0XHViMmU0KS48XC9wPlxyXG5cclxuPHA+JnF1b3Q7XHVjZDVjXHViMzAwIFx1YzljMFx1YWMwMVx1YjNjNCZxdW90O1x1YjI5NCBOXHVhYzFjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWM5YzBcdWFjMDFcdWIzYzQgXHVjOTExIFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdmMFx1YjM3MCZuYnNwO1x1Yzc3NCBcdWMyODhcdWQzN2MgXHVjZWY0XHVkNGU4XHVkMTMwXHVjNWQwXHViMjk0IFx1ZDJiOVx1Yzc3NFx1ZDU1YyBcdWFlMzBcdWIyYTVcdWM3NzQgXHVjNzg4XHViMjk0XHViMzcwLCBOXHVhYzFjXHVjNzU4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOCBcdWM5MTEgXHViNTMxIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgKFx1YjJmOVx1YzJlMFx1Yzc3NCkgJnF1b3Q7XHVjZDVjXHVjNmIwXHVjMTIwIFx1Y2M5OFx1YjlhYyBcdWIzMDBcdWMwYzEmcXVvdDtcdWM3M2NcdWI4NWMmbmJzcDtcdWM5YzBcdWM4MTVcdWQ1NThcdWM1ZWMgXHVkNTc0XHViMmY5IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBcdWJiMzRcdWM4NzBcdWFjNzQgMVx1YzJkY1x1YWMwNFx1YjljY1x1YzVkMCBcdWMyZTRcdWQ1ODlcdWI0MThcdWIzYzRcdWI4NWQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgTiA9IDMsIEggPSBbMiwgNCwgNl0sIEQgPSBbMywgNSwgOF1cdWM3NzRcdWI3N2MgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVhY2JkXHVjNmIwLCAxXHViYzg4XHViZDgwXHVkMTMwIDNcdWJjODggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWMyZTRcdWQ1ODlcdWM3NDQgXHVkNTU4XHVhY2UwIDNcdWJjODggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1YzJlNFx1ZDU4OVx1YzJkY1x1YWMwNFx1Yzc0NCAxXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM5YzBcdWM4MTVcdWQ1ODhcdWIyZTRcdWJhNzQsPFwvcD5cclxuXHJcbjxwPjFcdWJjODggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YzljMFx1YWUwOFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMgMlx1YzJkY1x1YWMwNCBcdWQ2YzRcdWM1ZDAgXHViMDVkXHViMDk4XHViYTcwIChDWzFdID0gMiksIDJcdWJjODhcdWM3NDAgXHVhZGY4XHViODVjXHViZDgwXHVkMTMwIDRcdWMyZGNcdWFjMDQgXHVkNmM0XHVjNWQwIFx1YjA1ZFx1YjA5OFx1YWNlMCAoQ1syXSA9IDYpLCAzXHViYzg4XHVjNzQwIFx1YWRmOFx1Yjg1Y1x1YmQ4MFx1ZDEzMCAxXHVjMmRjXHVhYzA0IFx1ZDZjNFx1YzVkMCBcdWIwNWRcdWIwOThcdWMxMWMgQ1szXSA9IDdcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViNTRjIFx1YWMwMSBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHVjOWMwXHVhYzAxXHViM2M0XHViMjk0IDAsIDEsIDBcdWM3NzRcdWJhNzAsIFx1Yzc3NCBcdWM5MTEgXHVjZDVjXHViMzAwXHVhYzEyXHVjNzc0IDFcdWM3NzRcdWJiYzBcdWI4NWMgXHVjZDVjXHViMzAwIFx1YzljMFx1YWMwMVx1YjNjNFx1YjI5NCAxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMTlcdWM3NDAgXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIDNcdWJjODggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHViZDgwXHVkMTMwIDFcdWJjODggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVhZTRjXHVjOWMwIFx1YzVlZFx1YzIxY1x1YzczY1x1Yjg1YyBcdWMyZTRcdWQ1ODlcdWQ1NThcdWFjZTAsIDNcdWJjODggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzU4IFx1YzJlNFx1ZDU4OVx1YzJkY1x1YWMwNFx1Yzc0NCAxXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM5YzBcdWM4MTVcdWQ1ODhcdWIyZTRcdWJhNzQsPFwvcD5cclxuXHJcbjxwPjNcdWJjODggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YzljMFx1YWUwOFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMgMVx1YzJkY1x1YWMwNCBcdWQ2YzRcdWM1ZDAgXHViMDVkXHViMDk4XHViYTcwIChDWzNdID0gMSksIDJcdWJjODhcdWM3NDAgXHVhZGY4XHViODVjXHViZDgwXHVkMTMwIDRcdWMyZGNcdWFjMDQgXHVkNmM0IChDWzJdID0gNSksIDFcdWJjODhcdWM3NDAgXHVhZGY4XHViODVjXHViZDgwXHVkMTMwIDJcdWMyZGNcdWFjMDQgXHVkNmM0XHVjNWQwIFx1YjA1ZFx1YjA5OFx1YzExYyBDWzFdID0gN1x1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI1NGMgXHVhYzAxIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWM5YzBcdWFjMDFcdWIzYzRcdWIyOTQgNCwgMCwgMFx1Yzc3NFx1YmE3MCwmbmJzcDtcdWM3NzQgXHVjOTExIFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc3NCA0XHVjNzc0XHViYmMwXHViODVjIFx1Y2Q1Y1x1YjMwMCBcdWM5YzBcdWFjMDFcdWIzYzRcdWIyOTQgNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYzI5XHViYzk1XHVjNzc0IFx1Y2Q1Y1x1YjMwMCBcdWM5YzBcdWFjMDFcdWIzYzRcdWI5N2MgXHVjZDVjXHVjMThjXHVkNjU0IFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBOXHVhYzFjXHVjNzU4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWMyZTRcdWQ1ODlcdWMyZGNcdWFjMDRcdWFjZmMgXHVkNzZjXHViOWRkIFx1YjM3MFx1YjRkY1x1Yjc3Y1x1Yzc3OFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIyZWNcdWMxMzEgXHVhYzAwXHViMmE1XHVkNTVjIFx1Y2Q1Y1x1YjMwMCBcdWM5YzBcdWFjMDFcdWIzYzRcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0Jm5ic3A7XHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDA2YyBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjMTM4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWFkZjggXHVjOTExIFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjMmU0XHVkNTg5XHVjMmRjXHVhYzA0IEhbaV1cdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWQ3NmNcdWI5ZGQgXHViMzcwXHViNGRjXHViNzdjXHVjNzc4IERbaV1cdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWIyZWNcdWMxMzEgXHVhYzAwXHViMmE1XHVkNTVjIFx1Y2Q1Y1x1YjMwMCBcdWM5YzBcdWFjMDFcdWIzYzRcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IFQgJmxlOyAxMDxcL2xpPlxyXG5cdDxsaT4yJm5ic3A7JmxlOyBOICZsZTsgMTAwLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgSFtpXSwgRFtpXSAmbGU7IDEsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIxOTU5NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1cGVyY29tcHV0ZXIiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBuZWVkIHRvIHJ1biBOIGNvbXB1dGluZyBqb2JzIChpbiBzZXF1ZW5jZSkgb24gYSBzdXBlcmNvbXB1dGVyIGZvciB5b3VyIHJlc2VhcmNoLjxcL3A+XHJcblxyXG48cD5UaGUgam9icyBhcmUgbGFiZWxlZCBmcm9tIDEgdG8gTiAoaW5jbHVzaXZlKSwgYW5kIGpvYiBpIHdvdWxkIHJ1biBmb3IgSFtpXSBob3VycyBvbiB0aGUgc3VwZXJjb21wdXRlciBhbmQgaXRzIGRlc2lyZWQgZGVhZGxpbmUgaXMgRFtpXSBob3VycyBmcm9tIG5vdy48XC9wPlxyXG5cclxuPHA+QXMgd2UgaGF2ZSBOIGpvYnMsIHRoZXJlIGFyZSBOISBkaWZmZXJlbnQgd2F5cyB0byBleGVjdXRlIHRoZXNlIE4gam9icyBiYWNrLXRvLWJhY2suPFwvcD5cclxuXHJcbjxwPkxldCBDW2ldIGJlIHRoZSB0aW1lIChmcm9tIG5vdykgd2hlbiBqb2IgaSBmaW5pc2hlcyBydW5uaW5nLiBGb3IgY29udmVuaWVuY2UsIGxldCB1cyBkZWZpbmUgJnF1b3Q7bGF0ZW5lc3Mgb2Ygam9iIGkmcXVvdDsgdG8gYmUgbWF4KDAsIENbaV0gLSBEW2ldKS4gVGhhdCBpcywgaWYgdGhlIGpvYiBmaW5pc2hlcyBiZWZvcmUgaXRzIGRlc2lyZWQgZGVhZGxpbmUsIHRoZW4gaXRzIGxhdGVuZXNzIGlzIDAuPFwvcD5cclxuXHJcbjxwPiZxdW90O1RoZSBtYXhpbXVtIGxhdGVuZXNzJnF1b3Q7IGRlZmluZWQgYXMgdGhlIGxhcmdlc3QgbGF0ZW5lc3Mgb2YgTiBqb2JzLjxcL3A+XHJcblxyXG48cD5UaGUgc3VwZXJjb21wdXRlciBoYXMgYW4gaW50ZXJlc3RpbmcgZmVhdHVyZSwgd2hpY2ggYWxsb3dzIHlvdSB0byBjaG9vc2Ugb25lIGpvYiBhcyAmcXVvdDtoaWdoIHByaW9yaXR5JnF1b3Q7IHNvIHRoYXQgaXQgY2FuIHJ1biBmb3IgZXhhY3RseSAxIGhvdXIuPFwvcD5cclxuXHJcbjxwPkZvciBpbnN0YW5jZSwgc3VwcG9zZSBOID0gMywgSCA9IFsyLCA0LCA2XSwgRCA9IFszLCA1LCA4XS48XC9wPlxyXG5cclxuPHA+SWYgeW91IHdlcmUgdG8gcnVuIGpvYiAxLCBqb2IgMiwgYW5kIGpvYiAzIGluIHRoaXMgb3JkZXIsIGFuZCBkZXNpZ25hdGVkIGpvYiAzIGFzICZxdW90O2hpZ2ggcHJpb3JpdHkmcXVvdDssPFwvcD5cclxuXHJcbjxwPnRoZW4gam9iIDEgd2lsbCBmaW5pc2ggaW4gMiBob3VycyAoQ1sxXSA9IDIpLCBqb2IgMiB3aWxsIGZpbmlzaCBpbiA0IGhvdXJzIGFmdGVyIHRoYXQgKENbMl0gPSA2KSwgYW5kIGpvYiAzIHdpbGwgZmluaXNoIDEgaG91ciBhZnRlciB0aGF0IChDWzNdID0gNykuPFwvcD5cclxuXHJcbjxwPkxhdGVuZXNzIG9mIHRoZXNlIGpvYnMgaXMgMCwgMSwgYW5kIDAgKHJlc3BlY3RpdmVseSksIGFuZCB0aHVzIHRoZSBtYXhpbXVtIGxhdGVuZXNzIG9mIHRoaXMgc2NoZWR1bGUgaXMgMS48XC9wPlxyXG5cclxuPHA+SW4gdGhlIHNhbWUgZXhhbXBsZSwgaWYgeW91IHJ1biBqb2IgMywgam9iIDIsIGFuZCBqb2IgMSB3aXRoIGpvYiAzIGFzICZxdW90O2hpZ2ggcHJpb3JpdHkmcXVvdDssJm5ic3A7PFwvcD5cclxuXHJcbjxwPnRoZW4gam9iIDMgd2lsbCBmaW5pc2ggaW4gMSBob3VyIGZyb20gbm93IChDWzNdID0gMSksIGpvYiAyIHdpbGwgZmluaXNoIDQgaG91cnMgYWZ0ZXIgdGhhdCAoQ1syXSA9IDUpLCBhbmQgam9iIDEgd2lsbCBmaW5pc2ggMiBob3VycyBhZnRlciB0aGF0IChDWzFdID0gNykuPFwvcD5cclxuXHJcbjxwPkxhdGVuZXNzIGlzIDQsIDAsIGFuZCAwIGZvciBlYWNoIGpvYiwgYW5kIHRodXMgdGhlIG1heGltdW0gbGF0ZW5lc3MgaXMgNC48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBleGFtcGxlLCB0aGUgZmlyc3Qgc2NoZWR1bGUgbWluaW1pemVzIHRoZSBtYXhpbXVtIGxhdGVuZXNzLjxcL3A+XHJcblxyXG48cD5HaXZlbiBOIGpvYnMgd2l0aCB0aGVpciBleGVjdXRpb24gdGltZSBhbmQgZGVzaXJlZCBkZWFkbGluZXMsIGNhbGN1bGF0ZSB0aGUgc21hbGxlc3QgcG9zc2libGUgbWF4aW11bSBsYXRlbmVzcyB5b3UgY2FuIGFjaGlldmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBULjxcL3A+XHJcblxyXG48cD5FYWNoIHRlc3QgY2FzZSB3aWxsIGNvbnRhaW4gdGhyZWUgbGluZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiBOLCB0aGUgbnVtYmVyIG9mIGpvYnMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSB3aWxsIGNvbnRhaW4gTiBpbnRlZ2VycyAoc2VwYXJhdGVkIGJ5IGEgd2hpdGVzcGFjZSksIHJlcHJlc2VudGluZyBleGVjdXRpb24gdGltZSwgSFtpXS48XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgd2lsbCBjb250YWluIE4gaW50ZWdlcnMgKHNlcGFyYXRlZCBieSBhIHdoaXRlc3BhY2UpLCByZXByZXNlbnRpbmcgZGVzaXJlZCBkZWFkbGluZXMsIERbaV0uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB5b3UgbXVzdCBvdXRwdXQgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIG1heGltdW0gbGF0ZW5lc3MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgVCAmbGU7IDEwPFwvbGk+XHJcblx0PGxpPjImbmJzcDsmbGU7IE4gJmxlOyAxMDAsMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBIW2ldLCBEW2ldICZsZTsgMSwwMDA8XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==

시간 제한

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