시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 70 22 20 58.824%

문제

상근이네 자동차 공장에는 직원이 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가 주어진다.

다음 M개 줄에는 자동차 j의 복잡도 Fj가 주어진다.

1 ≤ Ti, Fj ≤ 10,000

출력

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

예제 입력 1

3 3
2
1
1
2
1
1

예제 출력 1

11

힌트

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

W3sicHJvYmxlbV9pZCI6IjI4MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZThcdWJjYTBcdWM3NzRcdWM1YjQgXHViY2E4XHVkMmI4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHVjNzkwXHViM2Q5XHVjYzI4IFx1YWNmNVx1YzdhNVx1YzVkMFx1YjI5NCBcdWM5YzFcdWM2ZDBcdWM3NzQgTlx1YmE4NSBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjZjVcdWM3YTVcdWM3NDAgXHVjNzkwXHViM2Q5XHVjYzI4XHViOTdjIFx1Y2VlOFx1YmNhMFx1Yzc3NFx1YzViNCBcdWJjYThcdWQyYjhcdWM1ZDAgXHVjNjJjXHViODI0XHViMTkzXHVhY2UwIFx1Y2MyOFx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YzljMVx1YzZkMFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzljMVx1YzZkMCAxXHVjNzQwIFx1Y2VlOFx1YmNhMFx1Yzc3NFx1YzViNCBcdWJjYThcdWQyYjhcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWFjZTAsIE5cdWM3NDAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzljMVx1YzZkMFx1Yzc3NCBcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MyOCBcdWQ1NWMgXHViMzAwXHViOTdjIFx1YjljY1x1YjRkY1x1YjgyNFx1YmE3NCwgXHVjOWMxXHVjNmQwIDEoXHVjMGMxXHVhZGZjKVx1Yzc3NFx1YmQ4MFx1ZDEzMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YmE3NCBcdWM5YzFcdWM2ZDAgMlx1YWMwMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhY2UwLCBcdWM5YzFcdWM2ZDAgMlx1YWMwMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMDVkXHViMGI0XHViYTc0IFx1YzljMVx1YzZkMCAzXHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM5YzFcdWM2ZDAgTlx1Yzc3NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMDVkXHViMGI0XHViYTc0IFx1YWRmOFx1YzgxY1x1YzU3YyBcdWNjMjhcdWFjMDAgXHVjNjQ0XHVjMTMxXHViNDE4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjYzI4IE1cdWIzMDBcdWI5N2MgXHViOWNjXHViNGRjXHViODI0XHViYTc0LCAxXHViZDgwXHVkMTMwIE1cdWJjODhcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Y2MyOFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjOWMxXHVjNmQwIGlcdWFjMDAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Yzc3Y1x1Yzc0NCBcdWIwNWRcdWIwYjRcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzJkY1x1YWMwNFx1Yzc0MCBUPHN1Yj5pPFwvc3ViPlx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWFjMDEgXHVjNzkwXHViM2Q5XHVjYzI4IGpcdWM3NTggXHViY2Y1XHVjN2ExXHViM2M0XHViMjk0IEY8c3ViPmo8XC9zdWI+XHVjNzc0XHViMmU0LiBcdWM5YzFcdWM2ZDAgaVx1YWMwMCBcdWM3OTBcdWIzZDlcdWNjMjggalx1Yzc1OCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjNjQ0XHViOGNjXHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NDAgVDxzdWI+aTxcL3N1Yj4qRjxzdWI+ajxcL3N1Yj5cdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMDVkXHViMGI4XHViMmU0XHViYTc0LCBcdWFkZjggXHVjYzI4XHViMjk0IFx1Yzk4OVx1YzJkYyBcdWIyZTRcdWM3NGMgXHVjOWMxXHVjNmQwXHVjNWQwXHVhYzhjIFx1YjExOFx1YWNhOFx1YzljNFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFkZjggXHViNTRjLCBcdWIyZTRcdWM3NGMgXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzc3Y1x1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1Yzc3Y1x1Yzc0MCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWIwNWRcdWIwYjRcdWFjZTAgXHViMmU0XHVjNzRjIFx1YzljMVx1YzZkMFx1YzVkMFx1YWM4YyBcdWNjMjhcdWI5N2MgXHViMTE4XHVhY2JjXHViMjk0XHViMzcwLCBcdWIyZTRcdWM3NGMgXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzc3Y1x1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzBjMVx1ZDY2OVx1Yzc3NCBcdWJjMWNcdWMwZGRcdWQ1NThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWFlMzBcdWIyZTRcdWI4MjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjNzc0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzljMVx1YzZkMFx1Yzc3NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzdjXHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmRjXHVhYzA0XHVhY2ZjIFx1YmFhOFx1YjRlMCBcdWM3OTBcdWIzZDlcdWNjMjhcdWM3NTggXHViY2Y1XHVjN2ExXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWNjMjhcdWI5N2MgXHViYWE4XHViNDUwIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOLCBNICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMVx1YzZkMCBpXHVjNzU4IFx1Yzc5MVx1YzVjNSBcdWMyZGNcdWFjMDQgVDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzkwXHViM2Q5XHVjYzI4IGpcdWM3NTggXHViY2Y1XHVjN2ExXHViM2M0IEY8c3ViPmo8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MSAmbGU7IFQ8c3ViPmk8XC9zdWI+LCBGPHN1Yj5qPFwvc3ViPiAmbGU7IDEwLDAwMDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzkwXHViM2Q5XHVjYzI4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+NFx1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwOThcdWJhNzQsIFx1YzljMVx1YzZkMCAxXHVjNzc0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjYzI4XHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjNjQ0XHViOGNjXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjOTg5XHVjMmRjIFx1YjJlNFx1Yzc0YyBcdWM5YzFcdWM2ZDBcdWM1ZDBcdWFjOGMgXHVjYzI4XHViOTdjIFx1YjExOFx1YWUzNFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWJjMTRcdWI4NWMgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWNjMjhcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YzljMVx1YzVjNVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IDdcdWJkODRcdWM3NzQgXHVjOWMwXHViMDljIFx1ZDZjNFx1YzVkMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5YzFcdWM2ZDBcdWM3NDAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWNjMjggXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBjOFx1YzljMFx1YjljYywgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM5YzFcdWM2ZDBcdWM3NDAgXHVjNTQ0XHVjOWMxIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjYzI4IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWIwNWRcdWIwYjRcdWM5YzAgXHVjNTRhXHVjNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgMVx1YmQ4NFx1Yzc0NCBcdWMyNmNcdWFjZTAgNVx1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwYWNcdWM3NDQgXHViNTRjLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2MyOFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjYzI4XHViMjk0IDdcdWJkODRcdWM3NzQgXHVjOWMwXHViMGFjXHVjNzQ0IFx1YjU0YyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjYzI4XHViMjk0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWM5YzAgOFx1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwYWNcdWM3NDQgXHViNTRjIFx1YzY0NFx1YzEzMVx1YjQxOFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWNjMjhcdWIyOTQgOVx1YmQ4NCwgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWNjMjhcdWIyOTQgMTFcdWJkODRcdWM3NzQgXHVjOWMwXHViMDljIFx1YjRhNFx1YzVkMCBcdWM2NDRcdWMxMzFcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjODE1XHViMmY1XHVjNzQwIDExXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgyMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRSQUtBIiwiZGVzY3JpcHRpb24iOiI8cD5BcyBtZW50aW9uZWQgYmVmb3JlLCB0aGVyZSBhcmUgTiB3b3JrZXJzIGluIE1pcmtvJnJzcXVvO3MgZmFjdG9yeS4gVGhleSBhcmUgbWFudWZhY3R1cmluZyBjYXJzIG9uIGEgY29udmV5b3IgYmVsdCwgaW4gYSBwaXBlbGluZSBmYXNoaW9uLiBXb3JrZXJzIGFyZSBkZW5vdGVkIGJ5IG51bWJlcnMgMSAmbmRhc2g7IGxlZnRtb3N0LCB0byBOIC0gcmlnaHRtb3N0LiBFYWNoIG9mIHRoZSB3b3JrZXJzIGRvZXMgaGlzIHNwZWNpZmljIGpvYiBhbmQgcmVxdWlyZXMgY2VydGFpbiBhbW91bnQgb2YgdGltZSB0byBjb21wbGV0ZSBpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UHJvZHVjdGlvbiBvZiBhIHNpbmdsZSBjYXIgc3RhcnRzIHdpdGggd29ya2VyICMxIChNaXJrbykuIEFmdGVyIGhlIGhhZCBmaW5pc2hlZCB3aXRoIGhpcyBwYXJ0IG9mIHRoZSBqb2IsIHdvcmtlciAjMiB0YWtlcyBvdmVyLCBhZnRlciBoaW0gIzMuLi4gV2hlbiB3b3JrZXIgI04gZmluaXNoZXMgd2l0aCBoaXMgcGFydCwgdGhlIGNhciBpcyBmaW5pc2hlZC4gTWlya28gYW5kIGhpcyB3b3JrZXJzIGhhdmUgdG8gcHJvZHVjZSBNIGNhcnMgYW5kIHRoZXkgbXVzdCBwcm9kdWNlIHRoZW0gaW4gb3JkZXIgMSB0byBNLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXZlcnkgd29ya2VyIGkgd2Uga25vdyBUPHN1Yj5pPFwvc3ViPiAtIHRpbWUgcmVxdWlyZWQgZm9yIGhpbSB0byBkbyBoaXMgcGFydCBvZiB0aGUgam9iLiBGb3IgZXZlcnkgY2FyIGogd2Uga25vdyBmYWN0b3Igb2YgYXNzZW1ibHkgY29tcGxleGl0eSBGPHN1Yj5qPFwvc3ViPi4gVGltZSBpbiBtaW51dGVzIGZvciB3b3JrZXIgaSB0byBmaW5pc2ggaGlzIHBhcnQgb2YgaGUgam9iIG9uIHRoZSBjYXIgaiBpcyBjb21wdXRlZCBhcyBhIHByb2R1Y3QgVDxzdWI+aTxcL3N1Yj5GPHN1Yj5qPFwvc3ViPi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWZ0ZXIgc29tZSB3b3JrZXIgaGFzIGZpbmlzaGVkIHdvcmtpbmcgb24gYSBjYXIsIGhlIGhhcyB0byBnaXZlIGl0IHRvIHRoZSBuZXh0IHdvcmtlciBpbnN0YW50bHksIHdpdGhvdXQgYW55IGRlbGF5ICh3ZWlyZCBjb21wYW55IHBvbGljeSkuIEZvciB0aGF0IHJlYXNvbiwgdGhlIHdvcmtlciByZWNlaXZpbmcgdGhlIGNhciBoYXMgdG8gYmUgZnJlZSAoaGUgbXVzdCBub3QgYmUgd29ya2luZyBvbiBzb21lIG90aGVyIGNhcikuIEluIG9yZGVyIHRvIGZ1bGZpbGwgdGhpcyBjb25kaXRpb24sIE1pcmtvIGhhcyB0byBjaG9vc2UgYSBnb29kIHRpbWluZyB0byBzdGFydCBidWlsZGluZyBhIG5ldyBjYXIuIFRvIGJlIGVmZmljaWVudCwgaGUmcnNxdW87bGwgd2FpdCBtaW5pbXVtIG51bWJlciBvZiBtaW51dGVzIHVudGlsIGhlIGlzIGNlcnRhaW4gdGhhdCBhbGwgb2YgdGhlIGNvbmRpdGlvbnMgZGVzY3JpYmVkIGFyZSBtZXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCB3aWxsLCBnaXZlbiB3b3JrZXIgdGltZXMgYW5kIGZhY3RvcnMgb2YgY29tcGxleGl0eSBmb3IgZWFjaCBjYXIsIGNvbXB1dGUgdG90YWwgdGltZSByZXF1aXJlZCBmb3IgcHJvZHVjaW5nIGFsbCBvZiB0aGUgY2Fycy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzIE4gKDEgJmxlOyBOICZsZTsgMTAwIDAwMCksIG51bWJlciBvZiB3b3JrZXJzLCBhbmQgTSAoMSAmbGU7IE0gJmxlOyAxMDAgMDAwKSwgbnVtYmVyIG9mIGNhcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPmktdGggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHdvcmtlciB0aW1lIFQ8c3ViPmk8XC9zdWI+IGZvciB0aGUgd29ya2VyIGkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPmotdGggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIGZhY3RvciBvZiBjb21wbGV4aXR5IEY8c3ViPmo8XC9zdWI+IGZvciB0aGUgY2FyIGouJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXNlIGNvbmRpdGlvbnMgaG9sZDogMSAmbGU7IFQ8c3ViPmk8XC9zdWI+ICZsZTsgMTAgMDAwLCAxICZsZTsgRjxzdWI+ajxcL3N1Yj4gJmxlOyAxMCAwMDAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgaGFzIHRvIGNvbnRhaW4gcmVxdWlyZWQgbnVtYmVyIG9mIG1pbnV0ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5BZnRlciBmb3VyIG1pbnV0ZXMsIGZpcnN0IHdvcmtlciBmaW5pc2hlcyB3b3JraW5nIG9uIHRoZSBmaXJzdCBjYXIuIEhlIG1pZ2h0IHN0YXJ0IHdvcmtpbmcgb24gdGhlIHNlY29uZCBjYXIgaW1tZWRpYXRlbHksIGJ1dCB0aGF0IHdvdWxkIHZpb2xhdGUgYSBjb25kaXRpb24gdGhhdCBjYXJzIGhhdmUgdG8gYmUgcGFzc2VkIHRvIG5leHQgd29ya2VycyBhcyBzb29uIGFzIHRoZXkmcnNxdW87cmUgZG9uZSAoYWZ0ZXIgc2V2ZW4gbWludXRlcyBzZWNvbmQgd29ya2VyIHdvdWxkIGZpbmlzaCB3b3JraW5nIG9uIGhpcyBwYXJ0IG9mIHNlY29uZCBjYXIsIGJ1dCB0aGUgdGhpcmQgd29ya2VyIHdvdWxkIG5vdCBiZSBmcmVlIHRvIHRha2Ugb3ZlciBhcyBoZSB3b3VsZCBzdGlsbCBiZSB3b3JraW5nIG9uIHRoZSBmaXJzdCBjYXIpLiBUaGF0IGlzIHRoZSByZWFzb24gcHJvZHVjdGlvbiBvZiB0aGUgc2Vjb25kIGNhciBpcyBzdGFydGVkIGFmdGVyIGZpdmUgbWludXRlcy4gUHJvZHVjdGlvbiBvZiB0aGUgdGhpcmQgY2FyIHN0YXJ0cyBhZnRlciBzZXZlbiBtaW51dGVzLiBGaXJzdCBjYXIgaXMgZmluaXNoZWQgYWZ0ZXIgZWlnaHQsIHNlY29uZCBhZnRlciBuaW5lIGFuZCB0aGlyZCBhZnRlciBlbGV2ZW4gc2Vjb25kcy4gVG90YWwgdGltZSBpcyB0aGVuIDExLiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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