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

문제

상근이네 자동차 공장에는 직원이 N명 있다. 이 공장은 자동차를 컨베이어 벨트에 올려놓고 차를 만든다. 직원은 1번부터 N번까지 번호가 매겨져 있다. 직원 1은 컨베이어 벨트의 가장 왼쪽에 있고, N은 오른쪽에 있다. 각 직원이 하는 일은 모두 다르다.

차 한 대를 만들려면, 직원 1(상근)이부터 작업을 시작한다. 상근이가 작업을 끝내면 직원 2가 작업을 시작하고, 직원 2가 작업을 끝내면 직원 3이 작업을 시작한다. 그리고 직원 N이 작업을 끝내면 그 때 차가 완성되는 것이다. 차 M대를 만들려면, 1부터 M번까지 순서대로 차를 만들어야 한다.

각 직원 i가 자신의 일을 끝내는데 필요한 시간은 Ti이다. 또, 각 자동차 j의 복잡도는 Fj이다. 직원 i가 자동차 j의 작업을 완료하는데 필요한 시간은 Ti*Fj가 된다.

어떤 직원이 자신의 작업을 끝낸다면, 그 차는 즉시 다음 직원에게 넘겨진다. 따라서, 그 때, 다음 직원이 일을 하고 있으면 안 된다.

모든 일은 상근이가 시작한다. 상근이는 위와 같이 어떤 직원이 작업을 끝내고 다음 직원에게 차를 넘겼는데, 다음 직원이 일을 하고 있는 상황이 발생하지 않게 하려고 한다. 그렇게 하기 위해서 상근이는 작업을 하지 않고 기다려야 하는 시간이 있다. 이때, 이 시간을 최소로 하려고 한다.

모든 직원이 자신의 일을 끝내는데 필요한 시간과 모든 자동차의 복잡도가 주어진다. 이때, 차를 모두 만들기 위해서 필요한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 100,000)

다음 N개 줄에는 직원 i의 작업 시간 Ti가 주어진다. (1 ≤ Ti ≤ 10,000)

다음 M개 줄에는 자동차 j의 복잡도 Fj가 주어진다. (1 ≤ Fj ≤ 10,000)

출력

첫째 줄에 자동차를 모두 만들기 위해 필요한 최소 시간을 출력한다.

예제 입력 1

3 3
2
1
1
2
1
1

예제 출력 1

11

4분이 지나면, 직원 1이 첫 번째 차를 만드는 작업을 완료한다. 그리고 즉시 다음 직원에게 차를 넘긴다. 하지만, 바로 두 번째 차를 만드는 직업을 시작하면 안 된다. 그 이유는 7분이 지난 후에, 두 번째 직원은 두 번째 차 작업을 끝냈지만, 세 번째 직원은 아직 첫 번째 차 작업을 끝내지 않았기 때문이다. 따라서, 상근이는 1분을 쉬고 5분이 지났을 때, 두 번째 차를 만들기 시작한다. 또, 세 번째 차는 7분이 지났을 때 시작한다. 첫 번째 차는 작업을 시작한지 8분이 지났을 때 완성되고, 두 번째 차는 9분, 세 번째 차는 11분이 지난 뒤에 완성된다. 따라서, 정답은 11이다.

예제 입력 2

3 3
2
3
3
2
1
2

예제 출력 2

29

예제 입력 3

4 5
3
2
2
2
3
1
2
1
2

예제 출력 3

55
W3sicHJvYmxlbV9pZCI6IjI4MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZThcdWJjYTBcdWM3NzRcdWM1YjQgXHViY2E4XHVkMmI4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHVjNzkwXHViM2Q5XHVjYzI4IFx1YWNmNVx1YzdhNVx1YzVkMFx1YjI5NCBcdWM5YzFcdWM2ZDBcdWM3NzQgTlx1YmE4NSBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjZjVcdWM3YTVcdWM3NDAgXHVjNzkwXHViM2Q5XHVjYzI4XHViOTdjIFx1Y2VlOFx1YmNhMFx1Yzc3NFx1YzViNCBcdWJjYThcdWQyYjhcdWM1ZDAgXHVjNjJjXHViODI0XHViMTkzXHVhY2UwIFx1Y2MyOFx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YzljMVx1YzZkMFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzljMVx1YzZkMCAxXHVjNzQwIFx1Y2VlOFx1YmNhMFx1Yzc3NFx1YzViNCBcdWJjYThcdWQyYjhcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWFjZTAsIE5cdWM3NDAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzljMVx1YzZkMFx1Yzc3NCBcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MyOCBcdWQ1NWMgXHViMzAwXHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YmE3NCwgXHVjOWMxXHVjNmQwIDEoXHVjMGMxXHVhZGZjKVx1Yzc3NFx1YmQ4MFx1ZDEzMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YmE3NCBcdWM5YzFcdWM2ZDAgMlx1YWMwMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhY2UwLCBcdWM5YzFcdWM2ZDAgMlx1YWMwMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMDVkXHViMGI0XHViYTc0IFx1YzljMVx1YzZkMCAzXHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM5YzFcdWM2ZDAgTlx1Yzc3NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMDVkXHViMGI0XHViYTc0IFx1YWRmOCBcdWI1NGMgXHVjYzI4XHVhYzAwIFx1YzY0NFx1YzEzMVx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Y2MyOCBNXHViMzAwXHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YmE3NCwgMVx1YmQ4MFx1ZDEzMCBNXHViYzg4XHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNjMjhcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzljMVx1YzZkMCBpXHVhYzAwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM3N2NcdWM3NDQgXHViMDVkXHViMGI0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NDAgVDxzdWI+aTxcL3N1Yj5cdWM3NzRcdWIyZTQuIFx1YjYxMCwgXHVhYzAxIFx1Yzc5MFx1YjNkOVx1Y2MyOCBqXHVjNzU4IFx1YmNmNVx1YzdhMVx1YjNjNFx1YjI5NCBGPHN1Yj5qPFwvc3ViPlx1Yzc3NFx1YjJlNC4gXHVjOWMxXHVjNmQwIGlcdWFjMDAgXHVjNzkwXHViM2Q5XHVjYzI4IGpcdWM3NTggXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YzY0NFx1YjhjY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNzQwIFQ8c3ViPmk8XC9zdWI+KkY8c3ViPmo8XC9zdWI+XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzljMVx1YzZkMFx1Yzc3NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBiOFx1YjJlNFx1YmE3NCwgXHVhZGY4IFx1Y2MyOFx1YjI5NCBcdWM5ODlcdWMyZGMgXHViMmU0XHVjNzRjIFx1YzljMVx1YzZkMFx1YzVkMFx1YWM4YyBcdWIxMThcdWFjYThcdWM5YzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVhZGY4IFx1YjU0YywgXHViMmU0XHVjNzRjIFx1YzljMVx1YzZkMFx1Yzc3NCBcdWM3N2NcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjNzdjXHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzViNFx1YjVhNCBcdWM5YzFcdWM2ZDBcdWM3NzQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YWNlMCBcdWIyZTRcdWM3NGMgXHVjOWMxXHVjNmQwXHVjNWQwXHVhYzhjIFx1Y2MyOFx1Yjk3YyBcdWIxMThcdWFjYmNcdWIyOTRcdWIzNzAsIFx1YjJlNFx1Yzc0YyBcdWM5YzFcdWM2ZDBcdWM3NzQgXHVjNzdjXHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0IFx1YmMxY1x1YzBkZFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViODA3XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YWUzMFx1YjJlNFx1YjgyNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM3N2NcdWM3NDQgXHViMDVkXHViMGI0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWFjZmMgXHViYWE4XHViNGUwIFx1Yzc5MFx1YjNkOVx1Y2MyOFx1Yzc1OCBcdWJjZjVcdWM3YTFcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1Y2MyOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4sIE0gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMxXHVjNmQwIGlcdWM3NTggXHVjNzkxXHVjNWM1IFx1YzJkY1x1YWMwNCBUPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxJm5ic3A7JmxlOyBUPHN1Yj5pPFwvc3ViPiAmbGU7IDEwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YjNkOVx1Y2MyOCBqXHVjNzU4IFx1YmNmNVx1YzdhMVx1YjNjNCBGPHN1Yj5qPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyBGPHN1Yj5qPFwvc3ViPiAmbGU7IDEwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc5MFx1YjNkOVx1Y2MyOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPjRcdWJkODRcdWM3NzQgXHVjOWMwXHViMDk4XHViYTc0LCBcdWM5YzFcdWM2ZDAgMVx1Yzc3NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Y2MyOFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YzY0NFx1YjhjY1x1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1Yzk4OVx1YzJkYyBcdWIyZTRcdWM3NGMgXHVjOWMxXHVjNmQwXHVjNWQwXHVhYzhjIFx1Y2MyOFx1Yjk3YyBcdWIxMThcdWFlMzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViYzE0XHViODVjIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjYzI4XHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWM5YzFcdWM1YzVcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgN1x1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHVkNmM0XHVjNWQwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzljMVx1YzZkMFx1Yzc0MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2MyOCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMDVkXHViMGM4XHVjOWMwXHViOWNjLCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzljMVx1YzZkMFx1Yzc0MCBcdWM1NDRcdWM5YzEgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWNjMjggXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YzljMCBcdWM1NGFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCAxXHViZDg0XHVjNzQ0IFx1YzI2Y1x1YWNlMCA1XHViZDg0XHVjNzc0IFx1YzljMFx1YjBhY1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjYzI4XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWNjMjhcdWIyOTQgN1x1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwYWNcdWM3NDQgXHViNTRjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWNjMjhcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YzljMCA4XHViZDg0XHVjNzc0IFx1YzljMFx1YjBhY1x1Yzc0NCBcdWI1NGMgXHVjNjQ0XHVjMTMxXHViNDE4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2MyOFx1YjI5NCA5XHViZDg0LCBcdWMxMzggXHViYzg4XHVjOWY4IFx1Y2MyOFx1YjI5NCAxMVx1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHViNGE0XHVjNWQwIFx1YzY0NFx1YzEzMVx1YjQxY1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM4MTVcdWIyZjVcdWM3NDAgMTFcdWM3NzRcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjgyMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRSQUtBIiwiZGVzY3JpcHRpb24iOiI8cD5BcyBtZW50aW9uZWQgYmVmb3JlLCB0aGVyZSBhcmUgTiB3b3JrZXJzIGluIE1pcmtvJnJzcXVvO3MgZmFjdG9yeS4gVGhleSBhcmUgbWFudWZhY3R1cmluZyBjYXJzIG9uIGEgY29udmV5b3IgYmVsdCwgaW4gYSBwaXBlbGluZSBmYXNoaW9uLiBXb3JrZXJzIGFyZSBkZW5vdGVkIGJ5IG51bWJlcnMgMSAmbmRhc2g7IGxlZnRtb3N0LCB0byBOIC0gcmlnaHRtb3N0LiBFYWNoIG9mIHRoZSB3b3JrZXJzIGRvZXMgaGlzIHNwZWNpZmljIGpvYiBhbmQgcmVxdWlyZXMgY2VydGFpbiBhbW91bnQgb2YgdGltZSB0byBjb21wbGV0ZSBpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UHJvZHVjdGlvbiBvZiBhIHNpbmdsZSBjYXIgc3RhcnRzIHdpdGggd29ya2VyICMxIChNaXJrbykuIEFmdGVyIGhlIGhhZCBmaW5pc2hlZCB3aXRoIGhpcyBwYXJ0IG9mIHRoZSBqb2IsIHdvcmtlciAjMiB0YWtlcyBvdmVyLCBhZnRlciBoaW0gIzMuLi4gV2hlbiB3b3JrZXIgI04gZmluaXNoZXMgd2l0aCBoaXMgcGFydCwgdGhlIGNhciBpcyBmaW5pc2hlZC4gTWlya28gYW5kIGhpcyB3b3JrZXJzIGhhdmUgdG8gcHJvZHVjZSBNIGNhcnMgYW5kIHRoZXkgbXVzdCBwcm9kdWNlIHRoZW0gaW4gb3JkZXIgMSB0byBNLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXZlcnkgd29ya2VyIGkgd2Uga25vdyBUPHN1Yj5pPFwvc3ViPiAtIHRpbWUgcmVxdWlyZWQgZm9yIGhpbSB0byBkbyBoaXMgcGFydCBvZiB0aGUgam9iLiBGb3IgZXZlcnkgY2FyIGogd2Uga25vdyBmYWN0b3Igb2YgYXNzZW1ibHkgY29tcGxleGl0eSBGPHN1Yj5qPFwvc3ViPi4gVGltZSBpbiBtaW51dGVzIGZvciB3b3JrZXIgaSB0byBmaW5pc2ggaGlzIHBhcnQgb2YgaGUgam9iIG9uIHRoZSBjYXIgaiBpcyBjb21wdXRlZCBhcyBhIHByb2R1Y3QgVDxzdWI+aTxcL3N1Yj5GPHN1Yj5qPFwvc3ViPi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWZ0ZXIgc29tZSB3b3JrZXIgaGFzIGZpbmlzaGVkIHdvcmtpbmcgb24gYSBjYXIsIGhlIGhhcyB0byBnaXZlIGl0IHRvIHRoZSBuZXh0IHdvcmtlciBpbnN0YW50bHksIHdpdGhvdXQgYW55IGRlbGF5ICh3ZWlyZCBjb21wYW55IHBvbGljeSkuIEZvciB0aGF0IHJlYXNvbiwgdGhlIHdvcmtlciByZWNlaXZpbmcgdGhlIGNhciBoYXMgdG8gYmUgZnJlZSAoaGUgbXVzdCBub3QgYmUgd29ya2luZyBvbiBzb21lIG90aGVyIGNhcikuIEluIG9yZGVyIHRvIGZ1bGZpbGwgdGhpcyBjb25kaXRpb24sIE1pcmtvIGhhcyB0byBjaG9vc2UgYSBnb29kIHRpbWluZyB0byBzdGFydCBidWlsZGluZyBhIG5ldyBjYXIuIFRvIGJlIGVmZmljaWVudCwgaGUmcnNxdW87bGwgd2FpdCBtaW5pbXVtIG51bWJlciBvZiBtaW51dGVzIHVudGlsIGhlIGlzIGNlcnRhaW4gdGhhdCBhbGwgb2YgdGhlIGNvbmRpdGlvbnMgZGVzY3JpYmVkIGFyZSBtZXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCB3aWxsLCBnaXZlbiB3b3JrZXIgdGltZXMgYW5kIGZhY3RvcnMgb2YgY29tcGxleGl0eSBmb3IgZWFjaCBjYXIsIGNvbXB1dGUgdG90YWwgdGltZSByZXF1aXJlZCBmb3IgcHJvZHVjaW5nIGFsbCBvZiB0aGUgY2Fycy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzIE4gKDEgJmxlOyBOICZsZTsgMTAwIDAwMCksIG51bWJlciBvZiB3b3JrZXJzLCBhbmQgTSAoMSAmbGU7IE0gJmxlOyAxMDAgMDAwKSwgbnVtYmVyIG9mIGNhcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPmktdGggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHdvcmtlciB0aW1lIFQ8c3ViPmk8XC9zdWI+IGZvciB0aGUgd29ya2VyIGkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPmotdGggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIGZhY3RvciBvZiBjb21wbGV4aXR5IEY8c3ViPmo8XC9zdWI+IGZvciB0aGUgY2FyIGouJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXNlIGNvbmRpdGlvbnMgaG9sZDogMSAmbGU7IFQ8c3ViPmk8XC9zdWI+ICZsZTsgMTAgMDAwLCAxICZsZTsgRjxzdWI+ajxcL3N1Yj4gJmxlOyAxMCAwMDAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgaGFzIHRvIGNvbnRhaW4gcmVxdWlyZWQgbnVtYmVyIG9mIG1pbnV0ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5BZnRlciBmb3VyIG1pbnV0ZXMsIGZpcnN0IHdvcmtlciBmaW5pc2hlcyB3b3JraW5nIG9uIHRoZSBmaXJzdCBjYXIuIEhlIG1pZ2h0IHN0YXJ0IHdvcmtpbmcgb24gdGhlIHNlY29uZCBjYXIgaW1tZWRpYXRlbHksIGJ1dCB0aGF0IHdvdWxkIHZpb2xhdGUgYSBjb25kaXRpb24gdGhhdCBjYXJzIGhhdmUgdG8gYmUgcGFzc2VkIHRvIG5leHQgd29ya2VycyBhcyBzb29uIGFzIHRoZXkmcnNxdW87cmUgZG9uZSAoYWZ0ZXIgc2V2ZW4gbWludXRlcyBzZWNvbmQgd29ya2VyIHdvdWxkIGZpbmlzaCB3b3JraW5nIG9uIGhpcyBwYXJ0IG9mIHNlY29uZCBjYXIsIGJ1dCB0aGUgdGhpcmQgd29ya2VyIHdvdWxkIG5vdCBiZSBmcmVlIHRvIHRha2Ugb3ZlciBhcyBoZSB3b3VsZCBzdGlsbCBiZSB3b3JraW5nIG9uIHRoZSBmaXJzdCBjYXIpLiBUaGF0IGlzIHRoZSByZWFzb24gcHJvZHVjdGlvbiBvZiB0aGUgc2Vjb25kIGNhciBpcyBzdGFydGVkIGFmdGVyIGZpdmUgbWludXRlcy4gUHJvZHVjdGlvbiBvZiB0aGUgdGhpcmQgY2FyIHN0YXJ0cyBhZnRlciBzZXZlbiBtaW51dGVzLiBGaXJzdCBjYXIgaXMgZmluaXNoZWQgYWZ0ZXIgZWlnaHQsIHNlY29uZCBhZnRlciBuaW5lIGFuZCB0aGlyZCBhZnRlciBlbGV2ZW4gc2Vjb25kcy4gVG90YWwgdGltZSBpcyB0aGVuIDExLiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5BZnRlciBmb3VyIG1pbnV0ZXMsIGZpcnN0IHdvcmtlciBmaW5pc2hlcyB3b3JraW5nIG9uIHRoZSBmaXJzdCBjYXIuIEhlIG1pZ2h0IHN0YXJ0IHdvcmtpbmcgb24gdGhlIHNlY29uZCBjYXIgaW1tZWRpYXRlbHksIGJ1dCB0aGF0IHdvdWxkIHZpb2xhdGUgYSBjb25kaXRpb24gdGhhdCBjYXJzIGhhdmUgdG8gYmUgcGFzc2VkIHRvIG5leHQgd29ya2VycyBhcyBzb29uIGFzIHRoZXkmcnNxdW87cmUgZG9uZSAoYWZ0ZXIgc2V2ZW4gbWludXRlcyBzZWNvbmQgd29ya2VyIHdvdWxkIGZpbmlzaCB3b3JraW5nIG9uIGhpcyBwYXJ0IG9mIHNlY29uZCBjYXIsIGJ1dCB0aGUgdGhpcmQgd29ya2VyIHdvdWxkIG5vdCBiZSBmcmVlIHRvIHRha2Ugb3ZlciBhcyBoZSB3b3VsZCBzdGlsbCBiZSB3b3JraW5nIG9uIHRoZSBmaXJzdCBjYXIpLiBUaGF0IGlzIHRoZSByZWFzb24gcHJvZHVjdGlvbiBvZiB0aGUgc2Vjb25kIGNhciBpcyBzdGFydGVkIGFmdGVyIGZpdmUgbWludXRlcy4gUHJvZHVjdGlvbiBvZiB0aGUgdGhpcmQgY2FyIHN0YXJ0cyBhZnRlciBzZXZlbiBtaW51dGVzLiBGaXJzdCBjYXIgaXMgZmluaXNoZWQgYWZ0ZXIgZWlnaHQsIHNlY29uZCBhZnRlciBuaW5lIGFuZCB0aGlyZCBhZnRlciBlbGV2ZW4gc2Vjb25kcy4gVG90YWwgdGltZSBpcyB0aGVuIDExLjxcL3A+XHJcbiJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #3 6번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013