시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 59 21 19 57.576%

문제

상근이네 자동차 공장에는 직원이 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+XHViYWE4XHViNGUwIFx1Yzc3Y1x1Yzc0MCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWIwNWRcdWIwYjRcdWFjZTAgXHViMmU0XHVjNzRjIFx1YzljMVx1YzZkMFx1YzVkMFx1YWM4YyBcdWNjMjhcdWI5N2MgXHViMTE4XHVhY2JjXHViMjk0XHViMzcwLCBcdWIyZTRcdWM3NGMgXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzc3Y1x1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzBjMVx1ZDY2OVx1Yzc3NCBcdWJjMWNcdWMwZGRcdWQ1NThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWFlMzBcdWIyZTRcdWI4MjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1Yzc3NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM5YzFcdWM2ZDBcdWM3NzQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Yzc3Y1x1Yzc0NCBcdWIwNWRcdWIwYjRcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzJkY1x1YWMwNFx1YWNmYyBcdWJhYThcdWI0ZTAgXHVjNzkwXHViM2Q5XHVjYzI4XHVjNzU4IFx1YmNmNVx1YzdhMVx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1Y2MyOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4sIE0gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMxXHVjNmQwIGlcdWM3NTggXHVjNzkxXHVjNWM1IFx1YzJkY1x1YWMwNCBUPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3OTBcdWIzZDlcdWNjMjggalx1Yzc1OCBcdWJjZjVcdWM3YTFcdWIzYzQgRjxzdWI+ajxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD4xICZsZTsgVDxzdWI+aTxcL3N1Yj4sIEY8c3ViPmo8XC9zdWI+ICZsZTsgMTAsMDAwPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3OTBcdWIzZDlcdWNjMjhcdWI5N2MgXHViYWE4XHViNDUwIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD40XHViZDg0XHVjNzc0IFx1YzljMFx1YjA5OFx1YmE3NCwgXHVjOWMxXHVjNmQwIDFcdWM3NzQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWNjMjhcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWM2NDRcdWI4Y2NcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM5ODlcdWMyZGMgXHViMmU0XHVjNzRjIFx1YzljMVx1YzZkMFx1YzVkMFx1YWM4YyBcdWNjMjhcdWI5N2MgXHViMTE4XHVhZTM0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YmMxNFx1Yjg1YyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2MyOFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjOWMxXHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgN1x1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHVkNmM0XHVjNWQwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzljMVx1YzZkMFx1Yzc0MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2MyOCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViMDVkXHViMGM4XHVjOWMwXHViOWNjLCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzljMVx1YzZkMFx1Yzc0MCBcdWM1NDRcdWM5YzEgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWNjMjggXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YzljMCBcdWM1NGFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCAxXHViZDg0XHVjNzQ0IFx1YzI2Y1x1YWNlMCA1XHViZDg0XHVjNzc0IFx1YzljMFx1YjBhY1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjYzI4XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWNjMjhcdWIyOTQgN1x1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwYWNcdWM3NDQgXHViNTRjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWNjMjhcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YzljMCA4XHViZDg0XHVjNzc0IFx1YzljMFx1YjBhY1x1Yzc0NCBcdWI1NGMgXHVjNjQ0XHVjMTMxXHViNDE4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2MyOFx1YjI5NCA5XHViZDg0LCBcdWMxMzggXHViYzg4XHVjOWY4IFx1Y2MyOFx1YjI5NCAxMVx1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHViNGE0XHVjNWQwIFx1YzY0NFx1YzEzMVx1YjQxY1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM4MTVcdWIyZjVcdWM3NDAgMTFcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODIxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVFJBS0EiLCJkZXNjcmlwdGlvbiI6IjxwPkFzIG1lbnRpb25lZCBiZWZvcmUsIHRoZXJlIGFyZSBOIHdvcmtlcnMgaW4gTWlya28mcnNxdW87cyBmYWN0b3J5LiBUaGV5IGFyZSBtYW51ZmFjdHVyaW5nIGNhcnMgb24gYSBjb252ZXlvciBiZWx0LCBpbiBhIHBpcGVsaW5lIGZhc2hpb24uIFdvcmtlcnMgYXJlIGRlbm90ZWQgYnkgbnVtYmVycyAxICZuZGFzaDsgbGVmdG1vc3QsIHRvIE4gLSByaWdodG1vc3QuIEVhY2ggb2YgdGhlIHdvcmtlcnMgZG9lcyBoaXMgc3BlY2lmaWMgam9iIGFuZCByZXF1aXJlcyBjZXJ0YWluIGFtb3VudCBvZiB0aW1lIHRvIGNvbXBsZXRlIGl0LiZuYnNwOzxcL3A+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