시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB665571.429%

문제

도윤이는 작은 마을에 살았다. 옆집에는 시형이가 살았고, 둘은 떼어놓을 수 없는 절친이다.

어느 날, 그들이 싸웠다. 시형이가 도윤이의 지하실에서 라키아 술과 닭장에서 달걀을 훔치는 것을 도윤이가 봤기 때문이다.

다음 날 아침에 일어났을 때, 시형이는 매우 놀랐다. 어제 밤에 도윤이가 둘의 집 사이에 울타리를 친 것을 봤기 때문이다. 도윤이의 울타리는 일렬로 나열된 다양한 높이의 판자로 이루어져 있다.

분노한 시형이는 도윤이의 울타리의 꼴도 보기 싫어서, 도윤이의 울타리 앞, 자기 쪽 마당에 더 큰 울타리를 짓기로 결심했다. 시형이는 도윤이의 판자를 가릴 자신의 판자를 도윤이의 판자 앞에 놓을 것이다. 즉, 도윤이의 판자 이상의 높이를 가진 판자를 그 앞에 세우겠다는 것이다.

하지만 시형이는 거지라서 집에 판자가 하나도 없다. 판자를 훔치는 것을 깜빡한 모양이다. 그래서 그는 제재소에서 일하는 그의 친구 태우를 불렀다. 태우는 판자를 가져왔는데, 각각의 보드는 높이와 가격이 달랐다. 불행하게도, 시형이와 태우가 울타리를 세우기 시작할 때, 그들은 판자가 짧아서 도윤이의 울타리를 못 덮을 수도 있다는 것을 알아차렸다. 어쨌든 그들은 울타리를 그냥 짓기로 했지만, 시형이는 도윤이의 판자를 덮는 것을 성공한 판자에 대해서만 태우에게 돈을 지불하기로 했다.

예를 들어, 높이가 4인 도윤이 판자의 앞에 높이가 3인 판자를 세우면 태우는 그 판자의 비용을 시형이에게서 받을 수 없다. 한편 높이가 3인 도윤이 판자의 앞에 높이가 5인 판자를 세우면 태우는 그 판자의 비용을 받을 수 있다.

태우가 싫지 않다면, 태우가 최대한 많은 돈을 받을 수 있도록 도와주자.

입력

첫 줄에 도윤이의 판자 개수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 100,000 이다.

둘째 줄에는 각각의 도윤이의 판자 높이를 나타내는 N개의 정수들이 주어진다. 높이는 1이상 10,000 이하이다.

뒤따르는 N개 줄에는 각각 2개의 수가 들어있다. 첫 번째 수는 태우가 가져온 판자의 높이이고, 두 번째 수는 가격이다. 높이와 가격은 1이상 10,000 이하이다.

태우의 판자는 입력받는 순서대로 1번부터 N번까지 번호가 매겨진다.

출력

첫 줄에는 태우가 시형이에게 받을 수 있는 최대 금액을 출력한다.

둘째 줄에는 도윤이의 울타리 앞에 놓을 판자의 번호를 순서대로 출력한다. 예를 들어 3번, 1번, 2번 판자를 순서대로 세운다면 3 1 2 를 출력한다.

참고: 최적의 배치 순서는 유일하지 않을 수 있다.

예제 입력 1

5
400 200 500 600 400
200 400
300 600
400 200
500 800
600 100

예제 출력 1

1700
4 2 1 5 3

예제 입력 2

8
70 40 80 70 50 60 20 30
30 10
30 20
30 25
60 15
60 5
50 30
40 5
40 5

예제 출력 2

95
8 6 1 7 5 4 2 3
W3sicHJvYmxlbV9pZCI6IjMxNDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHVjZTU4XHVjNzkwISIsImRlc2NyaXB0aW9uIjoiPHA+XHViM2M0XHVjNzI0XHVjNzc0XHViMjk0IFx1Yzc5MVx1Yzc0MCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHVjMGI0XHVjNTU4XHViMmU0LiBcdWM2MDZcdWM5ZDFcdWM1ZDBcdWIyOTQgXHVjMmRjXHVkNjE1XHVjNzc0XHVhYzAwIFx1YzBiNFx1YzU1OFx1YWNlMCwgXHViNDU4XHVjNzQwIFx1YjViY1x1YzViNFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YzgwOFx1Y2U1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViMjkwIFx1YjBhMCwgXHVhZGY4XHViNGU0XHVjNzc0IFx1YzJmOFx1YzZlMFx1YjJlNC4gXHVjMmRjXHVkNjE1XHVjNzc0XHVhYzAwIFx1YjNjNFx1YzcyNFx1Yzc3NFx1Yzc1OCBcdWM5YzBcdWQ1NThcdWMyZTRcdWM1ZDBcdWMxMWMgXHViNzdjXHVkMGE0XHVjNTQ0IFx1YzIyMFx1YWNmYyBcdWIyZWRcdWM3YTVcdWM1ZDBcdWMxMWMgXHViMmVjXHVhYzQwXHVjNzQ0IFx1ZDZkNFx1Y2U1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHViM2M0XHVjNzI0XHVjNzc0XHVhYzAwIFx1YmQyNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWIwYTAgXHVjNTQ0XHVjZTY4XHVjNWQwIFx1Yzc3Y1x1YzViNFx1YjBhY1x1Yzc0NCBcdWI1NGMsIFx1YzJkY1x1ZDYxNVx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHViMTgwXHViNzkwXHViMmU0LiBcdWM1YjRcdWM4MWMgXHViYzI0XHVjNWQwIFx1YjNjNFx1YzcyNFx1Yzc3NFx1YWMwMCBcdWI0NThcdWM3NTggXHVjOWQxIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHVjZTVjIFx1YWM4M1x1Yzc0NCBcdWJkMjRcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWIzYzRcdWM3MjRcdWM3NzRcdWM3NTggXHVjNmI4XHVkMGMwXHViOWFjXHViMjk0IFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWIwOThcdWM1ZjRcdWI0MWMgXHViMmU0XHVjNTkxXHVkNTVjIFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWQzMTBcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZDg0XHViMTc4XHVkNTVjIFx1YzJkY1x1ZDYxNVx1Yzc3NFx1YjI5NCBcdWIzYzRcdWM3MjRcdWM3NzRcdWM3NTggXHVjNmI4XHVkMGMwXHViOWFjXHVjNzU4IFx1YWYzNFx1YjNjNCBcdWJjZjRcdWFlMzAgXHVjMmViXHVjNWI0XHVjMTFjLCBcdWIzYzRcdWM3MjRcdWM3NzRcdWM3NTggXHVjNmI4XHVkMGMwXHViOWFjIFx1YzU1ZSwgXHVjNzkwXHVhZTMwIFx1Y2FiZCBcdWI5YzhcdWIyZjlcdWM1ZDAgXHViMzU0IFx1ZDA3MCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHVjOWQzXHVhZTMwXHViODVjIFx1YWNiMFx1YzJlY1x1ZDU4OFx1YjJlNC4gXHVjMmRjXHVkNjE1XHVjNzc0XHViMjk0IFx1YjNjNFx1YzcyNFx1Yzc3NFx1Yzc1OCBcdWQzMTBcdWM3OTBcdWI5N2MgXHVhYzAwXHViOWI0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWQzMTBcdWM3OTBcdWI5N2MgXHViM2M0XHVjNzI0XHVjNzc0XHVjNzU4IFx1ZDMxMFx1Yzc5MCBcdWM1NWVcdWM1ZDAgXHViMTkzXHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWIzYzRcdWM3MjRcdWM3NzRcdWM3NTggXHVkMzEwXHVjNzkwIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHVhYzAwXHVjOWM0IFx1ZDMxMFx1Yzc5MFx1Yjk3YyBcdWFkZjggXHVjNTVlXHVjNWQwIFx1YzEzOFx1YzZiMFx1YWNhMFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWMyZGNcdWQ2MTVcdWM3NzRcdWIyOTQgXHVhYzcwXHVjOWMwXHViNzdjXHVjMTFjIFx1YzlkMVx1YzVkMCBcdWQzMTBcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4XHViM2M0IFx1YzVjNlx1YjJlNC4gXHVkMzEwXHVjNzkwXHViOTdjIFx1ZDZkNFx1Y2U1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHVhZTVjXHViZTYxXHVkNTVjIFx1YmFhOFx1YzU5MVx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YWRmOFx1YjI5NCBcdWM4MWNcdWM3YWNcdWMxOGNcdWM1ZDBcdWMxMWMgXHVjNzdjXHVkNTU4XHViMjk0IFx1YWRmOFx1Yzc1OCBcdWNlNWNcdWFkNmMgXHVkMGRjXHVjNmIwXHViOTdjIFx1YmQ4OFx1YjgwMFx1YjJlNC4gXHVkMGRjXHVjNmIwXHViMjk0IFx1ZDMxMFx1Yzc5MFx1Yjk3YyBcdWFjMDBcdWM4MzhcdWM2NTRcdWIyOTRcdWIzNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJjZjRcdWI0ZGNcdWIyOTQgXHViMTkyXHVjNzc0XHVjNjQwIFx1YWMwMFx1YWNhOVx1Yzc3NCBcdWIyZWNcdWI3OTBcdWIyZTQuIFx1YmQ4OFx1ZDU4OVx1ZDU1OFx1YWM4Y1x1YjNjNCwgXHVjMmRjXHVkNjE1XHVjNzc0XHVjNjQwIFx1ZDBkY1x1YzZiMFx1YWMwMCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHVjMTM4XHVjNmIwXHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWI1NGMsIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWQzMTBcdWM3OTBcdWFjMDAgXHVjOWU3XHVjNTQ0XHVjMTFjIFx1YjNjNFx1YzcyNFx1Yzc3NFx1Yzc1OCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViYWJiIFx1YjM2ZVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWM1NDRcdWNjMjhcdWI4MzhcdWIyZTQuIFx1YzViNFx1Y2EwY1x1YjRlMCBcdWFkZjhcdWI0ZTRcdWM3NDAgXHVjNmI4XHVkMGMwXHViOWFjXHViOTdjIFx1YWRmOFx1YjBlNSBcdWM5ZDNcdWFlMzBcdWI4NWMgXHVkNTg4XHVjOWMwXHViOWNjLCBcdWMyZGNcdWQ2MTVcdWM3NzRcdWIyOTQgXHViM2M0XHVjNzI0XHVjNzc0XHVjNzU4IFx1ZDMxMFx1Yzc5MFx1Yjk3YyBcdWIzNmVcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzEzMVx1YWNmNVx1ZDU1YyBcdWQzMTBcdWM3OTBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViOWNjIFx1ZDBkY1x1YzZiMFx1YzVkMFx1YWM4YyBcdWIzYzhcdWM3NDQgXHVjOWMwXHViZDg4XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViMTkyXHVjNzc0XHVhYzAwIDRcdWM3NzggXHViM2M0XHVjNzI0XHVjNzc0IFx1ZDMxMFx1Yzc5MFx1Yzc1OCBcdWM1NWVcdWM1ZDAgXHViMTkyXHVjNzc0XHVhYzAwIDNcdWM3NzggXHVkMzEwXHVjNzkwXHViOTdjIFx1YzEzOFx1YzZiMFx1YmE3NCBcdWQwZGNcdWM2YjBcdWIyOTQgXHVhZGY4IFx1ZDMxMFx1Yzc5MFx1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjMmRjXHVkNjE1XHVjNzc0XHVjNWQwXHVhYzhjXHVjMTFjIFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWQ1NWNcdWQzYjggXHViMTkyXHVjNzc0XHVhYzAwIDNcdWM3NzggXHViM2M0XHVjNzI0XHVjNzc0IFx1ZDMxMFx1Yzc5MFx1Yzc1OCBcdWM1NWVcdWM1ZDAgXHViMTkyXHVjNzc0XHVhYzAwIDVcdWM3NzggXHVkMzEwXHVjNzkwXHViOTdjIFx1YzEzOFx1YzZiMFx1YmE3NCBcdWQwZGNcdWM2YjBcdWIyOTQgXHVhZGY4IFx1ZDMxMFx1Yzc5MFx1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NDQgXHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDBkY1x1YzZiMFx1YWMwMCBcdWMyZWJcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0LCBcdWQwZGNcdWM2YjBcdWFjMDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjljZVx1Yzc0MCBcdWIzYzhcdWM3NDQgXHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWIzYzRcdWM3MjRcdWM3NzRcdWM3NTggXHVkMzEwXHVjNzkwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAxICZsZTsgTiAmbGU7IDEwMCwwMDAgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzYzRcdWM3MjRcdWM3NzRcdWM3NTggXHVkMzEwXHVjNzkwIFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIxOTJcdWM3NzRcdWIyOTQgMVx1Yzc3NFx1YzBjMSAxMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0YTRcdWI1MzBcdWI5NzRcdWIyOTQgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxIDJcdWFjMWNcdWM3NTggXHVjMjE4XHVhYzAwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgXHVkMGRjXHVjNmIwXHVhYzAwIFx1YWMwMFx1YzgzOFx1YzYyOCBcdWQzMTBcdWM3OTBcdWM3NTggXHViMTkyXHVjNzc0XHVjNzc0XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIxOFx1YjI5NCBcdWFjMDBcdWFjYTlcdWM3NzRcdWIyZTQuIFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWFjMDBcdWFjYTlcdWM3NDAgMVx1Yzc3NFx1YzBjMSAxMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwZGNcdWM2YjBcdWM3NTggXHVkMzEwXHVjNzkwXHViMjk0IFx1Yzc4NVx1YjgyNVx1YmMxYlx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQwZGNcdWM2YjBcdWFjMDAgXHVjMmRjXHVkNjE1XHVjNzc0XHVjNWQwXHVhYzhjIFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFlMDhcdWM1NjFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1YzcyNFx1Yzc3NFx1Yzc1OCBcdWM2YjhcdWQwYzBcdWI5YWMgXHVjNTVlXHVjNWQwIFx1YjE5M1x1Yzc0NCBcdWQzMTBcdWM3OTBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgM1x1YmM4OCwgMVx1YmM4OCwgMlx1YmM4OCBcdWQzMTBcdWM3OTBcdWI5N2MgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzEzOFx1YzZiNFx1YjJlNFx1YmE3NCAzIDEgMiBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjMzhcdWFjZTA6IFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWJjMzBcdWNlNTggXHVjMjFjXHVjMTFjXHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTQzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiT0dSQURBIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGxpdmVkIG5leHQgZG9vciB0byBlYWNoIG90aGVyIGluIGEgc21hbGwgdmlsbGFnZSBhbmQgdGhleSB3ZXJlIGluc2VwYXJhYmxlIGZyaWVuZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk9uZSBkYXkgdGhleSBoYWQgYSBmaWdodCAoU2xhdmtvIHdlbnQgY3JhenkgYmVjYXVzZSBoZSBmb3VuZCBvdXQgTWlya28gd2FzIHN0ZWFsaW5nIHJha2lqYSBmcm9tIGhpcyBiYXNlbWVudCBhbmQgZWdncyBmcm9tIHRoZSBoZW5ob3VzZSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldoZW4gTWlya28gd29rZSB1cCB0aGUgbmV4dCBtb3JuaW5nLCBoZSB3YXMgc3VycHJpc2VkIHRvIHNlZSB0aGF0LCBkdXJpbmcgdGhlIG5pZ2h0LCBTbGF2a28gaGFkIGJ1aWx0IGEgZmVuY2UgYmV0d2VlbiB0aGVpciBob3VzZXMuIFNsYXZrbyYjMzk7cyBmZW5jZSBjb25zaXN0cyBvZiBOIGJvYXJkcyBvZiB2YXJ5aW5nIGhlaWdodHMgcGxhY2VkIGluIG9uZSByb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvLCBmdXJpb3VzLCBkZWNpZGVkIHRvIGJ1aWxkIGFuIGV2ZW4gYmlnZ2VyIGZlbmNlIG9uIGhpcyBzaWRlLCBpbiBmcm9udCBvZiBTbGF2a28mIzM5O3MsIHNvIGhlIGRvZXNuJiMzOTt0aGF2ZSB0byBsb29rIGF0IFNsYXZrbyYjMzk7cyBmZW5jZS4gSW4gZnJvbnQgb2YgZWFjaCBvZiBTbGF2a28mIzM5O3MgTiBib2FyZHMgaGUgd2FudHMgdG8gcHV0IG9uZSBvZiBoaXMgb3duIHdoaWNoIHdpbGwgY292ZXIgU2xhdmtvJiMzOTtzIGJvYXJkIChpbiBvdGhlciB3b3JkcywgaGUgd2FudHMgZWFjaCBvZiBoaXMgYm9hcmRzIHRvIGJlIGF0IGxlYXN0IGFzIGhpZ2ggYXMgU2xhdmtvJiMzOTtzIGJvYXJkIGl0IGlzIGluIGZyb250IG9mKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QnV0IE1pcmtvIGRvZXNuJiMzOTt0IGhhdmUgYW55IGJvYXJkcyBhdCBob21lIChoZSBmb3Jnb3QgdG8gc3RlYWwgdGhlbSBmcm9tIFNsYXZrbykgc28gaGUgY2FsbGVkIGhpcyBmcmllbmQgTGVhIHdobyAoY29udmVuaWVudGx5KSB3b3JrcyBpbiBhIHNhd21pbGwuIExlYSBicm91Z2h0IE4gYm9hcmRzOyBlYWNoIG9mIHRoZSBib2FyZHMgaGFzIGEgaGVpZ2h0IGFuZCBwcmljZS4gVW5mb3J0dW5hdGVseSwgd2hlbiB0aGV5IHN0YXJ0ZWQgcmFpc2luZyB0aGUgZmVuY2UsIHRoZXkgbm90aWNlZCB0aGF0IExlYSYjMzk7cyBib2FyZHMgbWF5IG5vdCBiZSBoaWdoIGVub3VnaCB0byBjb3ZlciBlbnRpcmUgU2xhdmtvJiMzOTtzIGZlbmNlLiBTbyB0aGV5IGFncmVlZCB0aGV5IHdpbGwgYnVpbGQgdGhlIGZlbmNlIGFueXdheSwgYnV0IE1pcmtvIHdpbGwgcGF5IG9ubHkgdGhvc2UgYm9hcmRzIHdoaWNoIHdpbGwgY292ZXIgU2xhdmtvJiMzOTtzIGJvYXJkcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIHdpbGwgaGVscCBMZWEgYXJyYW5nZSB0aGUgYm9hcmRzIGFuZCBtYWtlIHRoZSBsYXJnZXN0IHBvc3NpYmxlIHByb2ZpdC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBib2FyZHMgaW4gU2xhdmtvJiMzOTtzIGZlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgTiBpbnRlZ2VycywgdGhlIGhlaWdodHMgb2YgdGhlIGJvYXJkcyBpbiBTbGF2a28mIzM5O3MgZmVuY2UuIFRoZSBoZWlnaHQgb2YgZWFjaCBib2FyZCBpcyBiZXR3ZWVuIDEgYW5kIDEwIDAwMCwgaW5jbHVzaXZlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMsIHRoZSBoZWlnaHQgYW5kIHByaWNlIG9mIG9uZSBib2FyZCB3aGljaCBMZWEgYnJvdWdodC4gQm90aCBudW1iZXJzIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCAxMCAwMDAsIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGVhJiMzOTtzIGJvYXJkcyBhcmUgbnVtYmVyZWQgMSB0byBOLCBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSBhcmUgZ2l2ZW4uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBsYXJnZXN0IHByb2ZpdCBMZWEgY2FuIGFjaGlldmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBzaG91bGQgY29udGFpbiB0aGUgaW5kaWNlcyBvZiBMZWEmIzM5O3MgYm9hcmRzIGluIG9yZGVyIGluIHdoaWNoIHRoZXkgcHV0IHRoZW0gaW4gZnJvbnQgb2YgU2xhdmtvJiMzOTtzIGZlbmNlICZuZGFzaDsgdGhlIGZpcnN0IG51bWJlciBpcyB0aGUgaW5kZXggb2YgTGVhJiMzOTtzIGJvYXJkIHdoaWNoIHRoZXkgd2lsbCBwdXQgaW4gZnJvbnQgb2YgU2xhdmtvJiMzOTtzIGZpcnN0IGJvYXJkLCBhbmQgc28gb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIHRoZSBzZWNvbmQgbGluZSB3cml0ZSB0aGUgaW5kZXhlcyBvZiBMZWEmIzM5O3MgYm9hcmRzIGluIG9yZGVyIGluIHdoaWNoIHRoZXkgcHV0IHRoZW0gaW4gZnJvbnQgb2YgU2xhdmtvJiMzOTtzIGZlbmNlLiBTbyB0aGUgZmlyc3QgbnVtYmVyIGlzIHRoZSBpbmRleCBvZiBMZWEmIzM5O3MgYm9hcmQgdGhleSB3aWxsIHB1dCBpbiBmcm9udCBvZiBTbGF2a28mIzM5O3MgZmlyc3QgYm9hcmQsIGFuZCBzbyBvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogdGhlIG9wdGltYWwgYXJyYW5nZW1lbnQgb2YgdGhlIGJvYXJkcyBtYXkgbm90IGJlIHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Q2xhcmlmaWNhdGlvbiBmb3IgZmlyc3QgZXhhbXBsZTogdGhlIGhlaWdodHMgb2YgdGhlIGJvYXJkcyB3aGljaCBNaXJrbyBwdXRzIGluIGZyb250IG9mIFNsYXZrbyYjMzk7cyBmZW5jZSBhcmUgaW4gb3JkZXIgNTAwLCAzMDAsIDIwMCwgNjAwIGkgNDAwLiBMZWEgZ2V0cyA4MDAsIDYwMCwgMCwgMTAwIGFuZCAyMDAgZm9yIHRoZW0uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2007 > National Competition #1 - Seniors 3번