시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 117 25 23 50.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이다.

W3sicHJvYmxlbV9pZCI6IjI4MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZThcdWJjYTBcdWM3NzRcdWM1YjQgXHViY2E4XHVkMmI4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHVjNzkwXHViM2Q5XHVjYzI4IFx1YWNmNVx1YzdhNVx1YzVkMFx1YjI5NCBcdWM5YzFcdWM2ZDBcdWM3NzQgTlx1YmE4NSBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjZjVcdWM3YTVcdWM3NDAgXHVjNzkwXHViM2Q5XHVjYzI4XHViOTdjIFx1Y2VlOFx1YmNhMFx1Yzc3NFx1YzViNCBcdWJjYThcdWQyYjhcdWM1ZDAgXHVjNjJjXHViODI0XHViMTkzXHVhY2UwIFx1Y2MyOFx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YzljMVx1YzZkMFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzljMVx1YzZkMCAxXHVjNzQwIFx1Y2VlOFx1YmNhMFx1Yzc3NFx1YzViNCBcdWJjYThcdWQyYjhcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWFjZTAsIE5cdWM3NDAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzljMVx1YzZkMFx1Yzc3NCBcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MyOCBcdWQ1NWMgXHViMzAwXHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YmE3NCwgXHVjOWMxXHVjNmQwIDEoXHVjMGMxXHVhZGZjKVx1Yzc3NFx1YmQ4MFx1ZDEzMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YmE3NCBcdWM5YzFcdWM2ZDAgMlx1YWMwMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhY2UwLCBcdWM5YzFcdWM2ZDAgMlx1YWMwMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMDVkXHViMGI0XHViYTc0IFx1YzljMVx1YzZkMCAzXHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM5YzFcdWM2ZDAgTlx1Yzc3NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMDVkXHViMGI0XHViYTc0IFx1YWRmOCBcdWI1NGMgXHVjYzI4XHVhYzAwIFx1YzY0NFx1YzEzMVx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Y2MyOCBNXHViMzAwXHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YmE3NCwgMVx1YmQ4MFx1ZDEzMCBNXHViYzg4XHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNjMjhcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzljMVx1YzZkMCBpXHVhYzAwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM3N2NcdWM3NDQgXHViMDVkXHViMGI0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NDAgVDxzdWI+aTxcL3N1Yj5cdWM3NzRcdWIyZTQuIFx1YjYxMCwgXHVhYzAxIFx1Yzc5MFx1YjNkOVx1Y2MyOCBqXHVjNzU4IFx1YmNmNVx1YzdhMVx1YjNjNFx1YjI5NCBGPHN1Yj5qPFwvc3ViPlx1Yzc3NFx1YjJlNC4gXHVjOWMxXHVjNmQwIGlcdWFjMDAgXHVjNzkwXHViM2Q5XHVjYzI4IGpcdWM3NTggXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YzY0NFx1YjhjY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNzQwIFQ8c3ViPmk8XC9zdWI+KkY8c3ViPmo8XC9zdWI+XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzljMVx1YzZkMFx1Yzc3NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBiOFx1YjJlNFx1YmE3NCwgXHVhZGY4IFx1Y2MyOFx1YjI5NCBcdWM5ODlcdWMyZGMgXHViMmU0XHVjNzRjIFx1YzljMVx1YzZkMFx1YzVkMFx1YWM4YyBcdWIxMThcdWFjYThcdWM5YzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVhZGY4IFx1YjU0YywgXHViMmU0XHVjNzRjIFx1YzljMVx1YzZkMFx1Yzc3NCBcdWM3N2NcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjNzdjXHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzViNFx1YjVhNCBcdWM5YzFcdWM2ZDBcdWM3NzQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YWNlMCBcdWIyZTRcdWM3NGMgXHVjOWMxXHVjNmQwXHVjNWQwXHVhYzhjIFx1Y2MyOFx1Yjk3YyBcdWIxMThcdWFjYmNcdWIyOTRcdWIzNzAsIFx1YjJlNFx1Yzc0YyBcdWM5YzFcdWM2ZDBcdWM3NzQgXHVjNzdjXHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0IFx1YmMxY1x1YzBkZFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViODA3XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YWUzMFx1YjJlNFx1YjgyNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM3N2NcdWM3NDQgXHViMDVkXHViMGI0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWFjZmMgXHViYWE4XHViNGUwIFx1Yzc5MFx1YjNkOVx1Y2MyOFx1Yzc1OCBcdWJjZjVcdWM3YTFcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1Y2MyOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4sIE0gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMxXHVjNmQwIGlcdWM3NTggXHVjNzkxXHVjNWM1IFx1YzJkY1x1YWMwNCBUPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxJm5ic3A7JmxlOyBUPHN1Yj5pPFwvc3ViPiAmbGU7IDEwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YjNkOVx1Y2MyOCBqXHVjNzU4IFx1YmNmNVx1YzdhMVx1YjNjNCBGPHN1Yj5qPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyBGPHN1Yj5qPFwvc3ViPiAmbGU7IDEwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc5MFx1YjNkOVx1Y2MyOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjRcdWJkODRcdWM3NzQgXHVjOWMwXHViMDk4XHViYTc0LCBcdWM5YzFcdWM2ZDAgMVx1Yzc3NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Y2MyOFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YzY0NFx1YjhjY1x1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1Yzk4OVx1YzJkYyBcdWIyZTRcdWM3NGMgXHVjOWMxXHVjNmQwXHVjNWQwXHVhYzhjIFx1Y2MyOFx1Yjk3YyBcdWIxMThcdWFlMzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViYzE0XHViODVjIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjYzI4XHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWM5YzFcdWM1YzVcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgN1x1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHVkNmM0XHVjNWQwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzljMVx1YzZkMFx1Yzc0MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2MyOCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMDVkXHViMGM4XHVjOWMwXHViOWNjLCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzljMVx1YzZkMFx1Yzc0MCBcdWM1NDRcdWM5YzEgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWNjMjggXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YzljMCBcdWM1NGFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCAxXHViZDg0XHVjNzQ0IFx1YzI2Y1x1YWNlMCA1XHViZDg0XHVjNzc0IFx1YzljMFx1YjBhY1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjYzI4XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWNjMjhcdWIyOTQgN1x1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwYWNcdWM3NDQgXHViNTRjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWNjMjhcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YzljMCA4XHViZDg0XHVjNzc0IFx1YzljMFx1YjBhY1x1Yzc0NCBcdWI1NGMgXHVjNjQ0XHVjMTMxXHViNDE4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2MyOFx1YjI5NCA5XHViZDg0LCBcdWMxMzggXHViYzg4XHVjOWY4IFx1Y2MyOFx1YjI5NCAxMVx1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHViNGE0XHVjNWQwIFx1YzY0NFx1YzEzMVx1YjQxY1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM4MTVcdWIyZjVcdWM3NDAgMTFcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODIxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVFJBS0EiLCJkZXNjcmlwdGlvbiI6IjxwPkFzIG1lbnRpb25lZCBiZWZvcmUsIHRoZXJlIGFyZSBOIHdvcmtlcnMgaW4gTWlya28mcnNxdW87cyBmYWN0b3J5LiBUaGV5IGFyZSBtYW51ZmFjdHVyaW5nIGNhcnMgb24gYSBjb252ZXlvciBiZWx0LCBpbiBhIHBpcGVsaW5lIGZhc2hpb24uIFdvcmtlcnMgYXJlIGRlbm90ZWQgYnkgbnVtYmVycyAxICZuZGFzaDsgbGVmdG1vc3QsIHRvIE4gLSByaWdodG1vc3QuIEVhY2ggb2YgdGhlIHdvcmtlcnMgZG9lcyBoaXMgc3BlY2lmaWMgam9iIGFuZCByZXF1aXJlcyBjZXJ0YWluIGFtb3VudCBvZiB0aW1lIHRvIGNvbXBsZXRlIGl0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Qcm9kdWN0aW9uIG9mIGEgc2luZ2xlIGNhciBzdGFydHMgd2l0aCB3b3JrZXIgIzEgKE1pcmtvKS4gQWZ0ZXIgaGUgaGFkIGZpbmlzaGVkIHdpdGggaGlzIHBhcnQgb2YgdGhlIGpvYiwgd29ya2VyICMyIHRha2VzIG92ZXIsIGFmdGVyIGhpbSAjMy4uLiBXaGVuIHdvcmtlciAjTiBmaW5pc2hlcyB3aXRoIGhpcyBwYXJ0LCB0aGUgY2FyIGlzIGZpbmlzaGVkLiBNaXJrbyBhbmQgaGlzIHdvcmtlcnMgaGF2ZSB0byBwcm9kdWNlIE0gY2FycyBhbmQgdGhleSBtdXN0IHByb2R1Y2UgdGhlbSBpbiBvcmRlciAxIHRvIE0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBldmVyeSB3b3JrZXIgaSB3ZSBrbm93IFQ8c3ViPmk8XC9zdWI+IC0gdGltZSByZXF1aXJlZCBmb3IgaGltIHRvIGRvIGhpcyBwYXJ0IG9mIHRoZSBqb2IuIEZvciBldmVyeSBjYXIgaiB3ZSBrbm93IGZhY3RvciBvZiBhc3NlbWJseSBjb21wbGV4aXR5IEY8c3ViPmo8XC9zdWI+LiBUaW1lIGluIG1pbnV0ZXMgZm9yIHdvcmtlciBpIHRvIGZpbmlzaCBoaXMgcGFydCBvZiBoZSBqb2Igb24gdGhlIGNhciBqIGlzIGNvbXB1dGVkIGFzIGEgcHJvZHVjdCBUPHN1Yj5pPFwvc3ViPkY8c3ViPmo8XC9zdWI+LiZuYnNwOzxcL3A+XHJcblxyXG48cD5BZnRlciBzb21lIHdvcmtlciBoYXMgZmluaXNoZWQgd29ya2luZyBvbiBhIGNhciwgaGUgaGFzIHRvIGdpdmUgaXQgdG8gdGhlIG5leHQgd29ya2VyIGluc3RhbnRseSwgd2l0aG91dCBhbnkgZGVsYXkgKHdlaXJkIGNvbXBhbnkgcG9saWN5KS4gRm9yIHRoYXQgcmVhc29uLCB0aGUgd29ya2VyIHJlY2VpdmluZyB0aGUgY2FyIGhhcyB0byBiZSBmcmVlIChoZSBtdXN0IG5vdCBiZSB3b3JraW5nIG9uIHNvbWUgb3RoZXIgY2FyKS4gSW4gb3JkZXIgdG8gZnVsZmlsbCB0aGlzIGNvbmRpdGlvbiwgTWlya28gaGFzIHRvIGNob29zZSBhIGdvb2QgdGltaW5nIHRvIHN0YXJ0IGJ1aWxkaW5nIGEgbmV3IGNhci4gVG8gYmUgZWZmaWNpZW50LCBoZSZyc3F1bztsbCB3YWl0IG1pbmltdW0gbnVtYmVyIG9mIG1pbnV0ZXMgdW50aWwgaGUgaXMgY2VydGFpbiB0aGF0IGFsbCBvZiB0aGUgY29uZGl0aW9ucyBkZXNjcmliZWQgYXJlIG1ldC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIHdpbGwsIGdpdmVuIHdvcmtlciB0aW1lcyBhbmQgZmFjdG9ycyBvZiBjb21wbGV4aXR5IGZvciBlYWNoIGNhciwgY29tcHV0ZSB0b3RhbCB0aW1lIHJlcXVpcmVkIGZvciBwcm9kdWNpbmcgYWxsIG9mIHRoZSBjYXJzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBzcGFjZS1zZXBhcmF0ZWQgcG9zaXRpdmUgaW50ZWdlcnMgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSwgbnVtYmVyIG9mIHdvcmtlcnMsIGFuZCBNICgxICZsZTsgTSAmbGU7IDEwMCAwMDApLCBudW1iZXIgb2YgY2Fycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+aS10aCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgd29ya2VyIHRpbWUgVDxzdWI+aTxcL3N1Yj4gZm9yIHRoZSB3b3JrZXIgaS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+ai10aCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgZmFjdG9yIG9mIGNvbXBsZXhpdHkgRjxzdWI+ajxcL3N1Yj4gZm9yIHRoZSBjYXIgai4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlc2UgY29uZGl0aW9ucyBob2xkOiAxICZsZTsgVDxzdWI+aTxcL3N1Yj4gJmxlOyAxMCAwMDAsIDEgJmxlOyBGPHN1Yj5qPFwvc3ViPiAmbGU7IDEwIDAwMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5GaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBoYXMgdG8gY29udGFpbiByZXF1aXJlZCBudW1iZXIgb2YgbWludXRlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkFmdGVyIGZvdXIgbWludXRlcywgZmlyc3Qgd29ya2VyIGZpbmlzaGVzIHdvcmtpbmcgb24gdGhlIGZpcnN0IGNhci4gSGUgbWlnaHQgc3RhcnQgd29ya2luZyBvbiB0aGUgc2Vjb25kIGNhciBpbW1lZGlhdGVseSwgYnV0IHRoYXQgd291bGQgdmlvbGF0ZSBhIGNvbmRpdGlvbiB0aGF0IGNhcnMgaGF2ZSB0byBiZSBwYXNzZWQgdG8gbmV4dCB3b3JrZXJzIGFzIHNvb24gYXMgdGhleSZyc3F1bztyZSBkb25lIChhZnRlciBzZXZlbiBtaW51dGVzIHNlY29uZCB3b3JrZXIgd291bGQgZmluaXNoIHdvcmtpbmcgb24gaGlzIHBhcnQgb2Ygc2Vjb25kIGNhciwgYnV0IHRoZSB0aGlyZCB3b3JrZXIgd291bGQgbm90IGJlIGZyZWUgdG8gdGFrZSBvdmVyIGFzIGhlIHdvdWxkIHN0aWxsIGJlIHdvcmtpbmcgb24gdGhlIGZpcnN0IGNhcikuIFRoYXQgaXMgdGhlIHJlYXNvbiBwcm9kdWN0aW9uIG9mIHRoZSBzZWNvbmQgY2FyIGlzIHN0YXJ0ZWQgYWZ0ZXIgZml2ZSBtaW51dGVzLiBQcm9kdWN0aW9uIG9mIHRoZSB0aGlyZCBjYXIgc3RhcnRzIGFmdGVyIHNldmVuIG1pbnV0ZXMuIEZpcnN0IGNhciBpcyBmaW5pc2hlZCBhZnRlciBlaWdodCwgc2Vjb25kIGFmdGVyIG5pbmUgYW5kIHRoaXJkIGFmdGVyIGVsZXZlbiBzZWNvbmRzLiBUb3RhbCB0aW1lIGlzIHRoZW4gMTEuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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