시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB96643534345.733%

문제

Juicy Orange Industry(JOI)는 맛있는 오렌지를 포장해서 출하하는 것이 주된 업무인 회사이다. 

JOI사에서는 수집한 N개의 오렌지를 상자에 넣어서 출하한다. 먼저, 오렌지는 공장에 있는 컨베이어 벨트 위에 나란히 놓아야 한다. 컨베이어 벨트 위에 놓여져있는 오렌지는 앞에서부터 순서대로 1부터 N까지 번호가 붙여져 있다. i번째 오렌지의 크기는 Ai이다.

그 다음 작업은 오렌지를 앞에서부터 순서대로 상자에 나눠서 넣는 것이다. 한 상자 넣는 오렌지의 번호는 연속해야 한다.

한 상자에는 최대 M개의 오렌지를 넣을 수 있다. 상자에 오렌지를 넣는 비용은 K + s × (a − b) 로 구할 수 있다. 여기서 a는 상자에 넣은 가장 큰 오렌지의 크기, b는 상자에 넣은 가장 작은 오렌지의 크기, s는 상자에 넣은 오렌지의 개수이다. K는 상자를 포장하는 비용이고, 모든 상자에 공통적으로 적용되는 값이다.

컨베이어 벨트 위에 놓여져 있는 오렌지의 정보와, 한 상자에 넣을 수 있는 오렌지 개수의 최댓값, 상자를 포장하는 비용 K가 주어졌을 때, 모든 오렌지를 포장하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 오렌지의 개수 N (1 ≤ N ≤ 20,000), 한 상자에 넣을 수 있는 오렌지 개수의 최댓값 M (1 ≤ M ≤ 1,000, M ≤ N), 상자를 포장하는 비용 K (0 ≤ k ≤ 1,000,000,000)가 주어진다.

둘째 줄부터 N개의 줄에는 오렌지의 크기 Ai (1 ≤ Ai ≤ 1,000,000,000)가 순서대로 주어진다. 

출력

첫째 줄에 모든 오렌지를 포장하는 비용의 최솟값을 출력한다.

서브태스크

번호배점제한
120

N ≤ 20.

250

N ≤ 2 000, M ≤ 100.

330

추가적인 제약 조건이 없다.

예제 입력 1

6 3 6
1
2
3
1
2
1

예제 출력 1

21

예제 입력 2

16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19

예제 출력 2

164

예제 입력 3

16 6 14
19
7
2
15
17
7
14
12
3
14
5
10
17
20
19
12

예제 출력 3

177

예제 입력 4

10 1 1000000000
1
1
1
1
1
1
1
1
1
1

예제 출력 4

10000000000
W3sicHJvYmxlbV9pZCI6IjExOTg1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNjI0XHViODBjXHVjOWMwIFx1Y2Q5Y1x1ZDU1OCIsImRlc2NyaXB0aW9uIjoiPHA+SnVpY3kgT3JhbmdlIEluZHVzdHJ5KEpPSSlcdWIyOTQgXHViOWRiXHVjNzg4XHViMjk0IFx1YzYyNFx1YjgwY1x1YzljMFx1Yjk3YyBcdWQzZWNcdWM3YTVcdWQ1NzRcdWMxMWMgXHVjZDljXHVkNTU4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM4ZmNcdWI0MWMgXHVjNWM1XHViYjM0XHVjNzc4IFx1ZDY4Y1x1YzBhY1x1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Sk9JXHVjMGFjXHVjNWQwXHVjMTFjXHViMjk0IFx1YzIxOFx1YzlkMVx1ZDU1YyBOXHVhYzFjXHVjNzU4IFx1YzYyNFx1YjgwY1x1YzljMFx1Yjk3YyBcdWMwYzFcdWM3OTBcdWM1ZDAgXHViMTIzXHVjNWI0XHVjMTFjIFx1Y2Q5Y1x1ZDU1OFx1ZDU1Y1x1YjJlNC4gXHViYTNjXHVjODAwLCBcdWM2MjRcdWI4MGNcdWM5YzBcdWIyOTQgXHVhY2Y1XHVjN2E1XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNlZThcdWJjYTBcdWM3NzRcdWM1YjQgXHViY2E4XHVkMmI4IFx1YzcwNFx1YzVkMCBcdWIwOThcdWI3ODBcdWQ3ODggXHViMTkzXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjZWU4XHViY2EwXHVjNzc0XHVjNWI0IFx1YmNhOFx1ZDJiOCBcdWM3MDRcdWM1ZDAgXHViMTkzXHVjNWVjXHVjODM4XHVjNzg4XHViMjk0IFx1YzYyNFx1YjgwY1x1YzljMFx1YjI5NCBcdWM1NWVcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWM2MjRcdWI4MGNcdWM5YzBcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IEE8c3ViPmk8XC9zdWI+XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFx1Yzc5MVx1YzVjNVx1Yzc0MCBcdWM2MjRcdWI4MGNcdWM5YzBcdWI5N2MgXHVjNTVlXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWMwYzFcdWM3OTBcdWM1ZDAgXHViMDk4XHViMjIwXHVjMTFjIFx1YjEyM1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDU1YyBcdWMwYzFcdWM3OTAgXHViMTIzXHViMjk0IFx1YzYyNFx1YjgwY1x1YzljMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgXHVjNWYwXHVjMThkXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTVjIFx1YzBjMVx1Yzc5MFx1YzVkMFx1YjI5NCBcdWNkNWNcdWIzMDAgTVx1YWMxY1x1Yzc1OCBcdWM2MjRcdWI4MGNcdWM5YzBcdWI5N2MgXHViMTIzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1Yzc5MFx1YzVkMCBcdWM2MjRcdWI4MGNcdWM5YzBcdWI5N2MgXHViMTIzXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0MCBLICsgcyAmdGltZXM7IChhICZtaW51czsgYikgXHViODVjIFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgYVx1YjI5NCBcdWMwYzFcdWM3OTBcdWM1ZDAgXHViMTIzXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjNjI0XHViODBjXHVjOWMwXHVjNzU4IFx1ZDA2Y1x1YWUzMCwgYlx1YjI5NCBcdWMwYzFcdWM3OTBcdWM1ZDAgXHViMTIzXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjNjI0XHViODBjXHVjOWMwXHVjNzU4IFx1ZDA2Y1x1YWUzMCwgc1x1YjI5NCBcdWMwYzFcdWM3OTBcdWM1ZDAgXHViMTIzXHVjNzQwIFx1YzYyNFx1YjgwY1x1YzljMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIEtcdWIyOTQgXHVjMGMxXHVjNzkwXHViOTdjIFx1ZDNlY1x1YzdhNVx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NzRcdWFjZTAsIFx1YmFhOFx1YjRlMCBcdWMwYzFcdWM3OTBcdWM1ZDAgXHVhY2Y1XHVkMWI1XHVjODAxXHVjNzNjXHViODVjIFx1YzgwMVx1YzZhOVx1YjQxOFx1YjI5NCBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2VlOFx1YmNhMFx1Yzc3NFx1YzViNCBcdWJjYThcdWQyYjggXHVjNzA0XHVjNWQwIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHVjNjI0XHViODBjXHVjOWMwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YzY0MCwgXHVkNTVjIFx1YzBjMVx1Yzc5MFx1YzVkMCBcdWIxMjNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MjRcdWI4MGNcdWM5YzAgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMiwgXHVjMGMxXHVjNzkwXHViOTdjIFx1ZDNlY1x1YzdhNVx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM2YTkgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVjNjI0XHViODBjXHVjOWMwXHViOTdjIFx1ZDNlY1x1YzdhNVx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2MjRcdWI4MGNcdWM5YzBcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDEgJmxlOyBOICZsZTsgMjAsMDAwKSwgXHVkNTVjIFx1YzBjMVx1Yzc5MFx1YzVkMCBcdWIxMjNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MjRcdWI4MGNcdWM5YzAgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMiBNICgxICZsZTsgTSAmbGU7IDEsMDAwLCBNICZsZTsgTiksIFx1YzBjMVx1Yzc5MFx1Yjk3YyBcdWQzZWNcdWM3YTVcdWQ1NThcdWIyOTQgXHViZTQ0XHVjNmE5IEsgKDAgJmxlOyBrICZsZTsgMSwwMDAsMDAwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzYyNFx1YjgwY1x1YzljMFx1Yzc1OCBcdWQwNmNcdWFlMzAgQTxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCwwMDApXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhYThcdWI0ZTAgXHVjNjI0XHViODBjXHVjOWMwXHViOTdjIFx1ZDNlY1x1YzdhNVx1ZDU1OFx1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzdWJ0YXNrMSI6IjxwPk4gJmxlOyAyMC48XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPk4gJmxlOyAyIDAwMCwgTSAmbGU7IDEwMC48XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPlx1Y2Q5NFx1YWMwMFx1YzgwMVx1Yzc3OCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0XHVjNzc0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIxMTk4NSIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1MzBhYVx1MzBlY1x1MzBmM1x1MzBiOFx1MzA2ZVx1NTFmYVx1ODM3NyAoT3JhbmdlcykiLCJkZXNjcmlwdGlvbiI6IjxwPlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZiBKdWljeSBPcmFuZ2UgSW5kdXN0cnkgXHU3OTNlXHUzMDkyXHU3N2U1XHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDhiXHUzMDYwXHUzMDhkXHUzMDQ2XHUzMDRiPyBcdTMwNTNcdTMwNmVcdTRmMWFcdTc5M2VcdTMwNmVcdTY5NmRcdTUyZDlcdTMwNmZcdTdmOGVcdTU0NzNcdTMwNTdcdTMwNDRcdTMwYWFcdTMwZWNcdTMwZjNcdTMwYjhcdTMwOTJcdTY4M2RcdTU3ZjlcdTMwNTdcdTMwNjZcdTUxZmFcdTgzNzdcdTMwNTlcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTMwNTNcdTMwNTNcdTMwNjdcdTMwNmZcdTc1NjVcdTMwNTdcdTMwNjYgSk9JIFx1NzkzZVx1MzA2OFx1NTQ3Y1x1MzA3Nlx1ZmYwZTxcL3A+XHJcblxyXG48cD5KT0kgXHU3OTNlXHUzMDY3XHUzMDZmXHVmZjBjXHU1M2NlXHU3YTZiXHUzMDU1XHUzMDhjXHUzMDVmIE4gXHU1MDBiXHUzMDZlXHUzMGFhXHUzMGVjXHUzMGYzXHUzMGI4XHUzMDkyXHU3YmIxXHU4YTcwXHUzMDgxXHUzMDU3XHUzMDY2XHU1MWZhXHU4Mzc3XHUzMDU5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHUzMDZhXHUzMDYzXHUzMDVmXHVmZjBlXHUzMGFhXHUzMGVjXHUzMGYzXHUzMGI4XHUzMDZmXHU1ZGU1XHU1ODM0XHUzMDZiXHUzMDQyXHUzMDhiXHUzMGQ5XHUzMGViXHUzMGM4XHUzMGIzXHUzMGYzXHUzMGQ5XHUzMGEyXHUzMDZlXHU0ZTBhXHUzMDZiXHU0ZTI2XHUzMDc5XHUzMDg5XHUzMDhjXHUzMDY2XHUzMDRhXHUzMDhhXHVmZjBjXHUzMGQ5XHUzMGViXHUzMGM4XHUzMGIzXHUzMGYzXHUzMGQ5XHUzMGEyXHUzMDZlXHU1MjRkXHUzMDRiXHUzMDg5XHU5ODA2XHU3NTZhXHUzMDZiIDEgXHUzMDRiXHUzMDg5IE4gXHUzMDdlXHUzMDY3XHUzMDZlXHU3NTZhXHU1M2Y3XHUzMDRjXHU0ZWQ4XHUzMDUxXHUzMDg5XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMGFhXHUzMGVjXHUzMGYzXHUzMGI4XHUzMDZmXHU1OTI3XHU1YzBmXHUzMDU1XHUzMDdlXHUzMDU2XHUzMDdlXHUzMDY3XHUzMDQyXHUzMDhhXHVmZjBjXHUzMGFhXHUzMGVjXHUzMGYzXHUzMGI4IGkgKDEgXHUyMjY2IGkgXHUyMjY2IE4pIFx1MzA2ZVx1NTkyN1x1MzA0ZFx1MzA1NVx1MzA2ZiBBaSBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHUzMDUzXHUzMDhjXHUzMDg5XHUzMDZlXHUzMGFhXHUzMGVjXHUzMGYzXHUzMGI4XHUzMDkyXHU1MjRkXHUzMDRiXHUzMDg5XHU5ODA2XHU3NTZhXHUzMDZiXHUzMDQ0XHUzMDRmXHUzMDY0XHUzMDRiXHUzMDZlXHU3YmIxXHUzMDZiXHU1MjA2XHUzMDUxXHUzMDY2XHU4YTcwXHUzMDgxXHUzMDhiXHVmZjBlXHUzMDcyXHUzMDY4XHUzMDY0XHUzMDZlXHU3YmIxXHUzMDZiXHUzMDZmXHU5MDIzXHU3ZDlhXHUzMDU3XHUzMDVmXHU3NTZhXHU1M2Y3XHUzMDZlXHUzMGFhXHUzMGVjXHUzMGYzXHUzMGI4XHUzMDU3XHUzMDRiXHU4YTcwXHUzMDgxXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1MzA3Mlx1MzA2OFx1MzA2NFx1MzA2ZVx1N2JiMVx1MzA2Ylx1MzA2Zlx1NjcwMFx1NTkyN1x1MzA2NyBNIFx1NTAwYlx1MzA3ZVx1MzA2N1x1MzA2ZVx1MzBhYVx1MzBlY1x1MzBmM1x1MzBiOFx1MzA5Mlx1OGE3MFx1MzA4MVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1ZmYwZVx1MzA0Mlx1MzA4Ylx1N2JiMVx1MzA2Ylx1MzA0NFx1MzA0Zlx1MzA2NFx1MzA0Ylx1MzA2ZVx1MzBhYVx1MzBlY1x1MzBmM1x1MzBiOFx1MzA5Mlx1OGE3MFx1MzA4MVx1MzA4Ylx1MzA1Zlx1MzA4MVx1MzA2Ylx1MzA0Ylx1MzA0Ylx1MzA4Ylx1MzBiM1x1MzBiOVx1MzBjOFx1MzA2Zlx1ZmYwY1x1N2JiMVx1MzA2Ylx1OGE3MFx1MzA4MVx1MzA4Ylx1NjcwMFx1NTkyN1x1MzA2ZVx1MzBhYVx1MzBlY1x1MzBmM1x1MzBiOFx1MzA2ZVx1NTkyN1x1MzA0ZFx1MzA1NVx1MzA5MiBhXHVmZjBjXHU3YmIxXHUzMDZiXHU4YTcwXHUzMDgxXHUzMDhiXHU2NzAwXHU1YzBmXHUzMDZlXHUzMGFhXHUzMGVjXHUzMGYzXHUzMGI4XHUzMDZlXHU1OTI3XHUzMDRkXHUzMDU1XHUzMDkyIGJcdWZmMGNcdTdiYjFcdTMwNmJcdThhNzBcdTMwODFcdTMwOGJcdTMwYWFcdTMwZWNcdTMwZjNcdTMwYjhcdTMwNmVcdTUwMGJcdTY1NzBcdTMwOTIgcyBcdTMwNjhcdTMwNTdcdTMwNWZcdTMwNjhcdTMwNGRcdTMwNmJcdWZmMGNLICsgcyAmdGltZXM7IChhICZtaW51czsgYikgXHUzMDY3XHU2YzQyXHUzMDgxXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHVmZjBlXHUzMDUzXHUzMDUzXHUzMDY3XHVmZjBjSyBcdTMwNmZcdTdiYjFcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNcdTMwNTlcdTMwNzlcdTMwNjZcdTMwNmVcdTdiYjFcdTMwNjdcdTUxNzFcdTkwMWFcdTMwNmVcdTUwMjRcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU5MDY5XHU1MjA3XHUzMDZhXHU1MDBiXHU2NTcwXHUzMDZlXHU3YmIxXHUzMDkyXHU3NTI4XHU2MTBmXHUzMDU3XHUzMDY2XHVmZjBjXHUzMDU5XHUzMDc5XHUzMDY2XHUzMDZlXHUzMGFhXHUzMGVjXHUzMGYzXHUzMGI4XHUzMDkyXHU5MDY5XHU1MjA3XHUzMDZiXHU3YmIxXHU4YTcwXHUzMDgxXHUzMDU5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDY3XHVmZjBjXHU3YmIxXHU4YTcwXHUzMDgxXHUzMDZiXHUzMDRiXHUzMDRiXHUzMDhiXHUzMGIzXHUzMGI5XHUzMGM4XHUzMDZlXHU3ZGNmXHU1NDhjXHUzMDkyXHUzMDY3XHUzMDRkXHUzMDhiXHUzMDYwXHUzMDUxXHU1YzBmXHUzMDU1XHUzMDRmXHUzMDU3XHUzMDVmXHUzMDQ0XHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1MzBkOVx1MzBlYlx1MzBjOFx1MzBiM1x1MzBmM1x1MzBkOVx1MzBhMlx1NGUwYVx1MzA2Ylx1NGUyNlx1MzA5M1x1MzA2N1x1MzA0NFx1MzA4Ylx1MzBhYVx1MzBlY1x1MzBmM1x1MzBiOFx1MzA2ZVx1NjBjNVx1NTgzMVx1MzA2OFx1ZmYwY1x1MzA3Mlx1MzA2OFx1MzA2NFx1MzA2ZVx1N2JiMVx1MzA2Ylx1OGE3MFx1MzA4MVx1MzA4OVx1MzA4Y1x1MzA4Ylx1MzBhYVx1MzBlY1x1MzBmM1x1MzBiOFx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA2ZVx1NjcwMFx1NTkyN1x1NTAyNFx1MzA0YVx1MzA4OFx1MzA3M1x1ZmYwY1x1N2JiMVx1MzA2Ylx1MzA0Ylx1MzA0Ylx1MzA4Ylx1MzBiM1x1MzBiOVx1MzBjOFx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1Zlx1MzA2OFx1MzA0ZFx1ZmYwY1x1N2JiMVx1OGE3MFx1MzA4MVx1MzA2Ylx1MzA0Ylx1MzA0Ylx1MzA4Ylx1MzBiM1x1MzBiOVx1MzBjOFx1MzA2ZVx1N2RjZlx1NTQ4Y1x1MzA2ZVx1NjcwMFx1NWMwZlx1NTAyNFx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU2YTE5XHU2ZTk2XHU1MTY1XHU1MjliXHUzMDRiXHUzMDg5XHU0ZWU1XHU0ZTBiXHUzMDZlXHU1MTY1XHU1MjliXHUzMDkyXHU4YWFkXHUzMDdmXHU4ZmJjXHUzMDgxXHVmZjBlPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdWZmMGMzIFx1NTAwYlx1MzA2ZVx1NjU3NFx1NjU3MCBOLCBNLCBLIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1MzA5Mlx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2OFx1MzA1N1x1MzA2Nlx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA2Zlx1ZmYwY1x1MzBhYVx1MzBlY1x1MzBmM1x1MzBiOFx1MzA0YyBOIFx1NTAwYlx1MzA0Mlx1MzA4YVx1ZmYwY1x1MzA3Mlx1MzA2OFx1MzA2NFx1MzA2ZVx1N2JiMVx1MzA2Ylx1OGE3MFx1MzA4MVx1MzA4OVx1MzA4Y1x1MzA4Ylx1MzBhYVx1MzBlY1x1MzBmM1x1MzBiOFx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA2ZVx1NjcwMFx1NTkyN1x1NTAyNFx1MzA0YyBNIFx1MzA2N1x1MzA0Mlx1MzA2M1x1MzA2Nlx1ZmYwY1x1N2JiMVx1MzA2Ylx1MzA0Ylx1MzA0Ylx1MzA4Ylx1MzBiM1x1MzBiOVx1MzBjOFx1MzA0YyBLIFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTdkOWFcdTMwNGYgTiBcdTg4NGNcdTMwNmVcdTMwNDZcdTMwNjFcdTMwNmUgaSBcdTg4NGNcdTc2ZWUgKDEgXHUyMjY2IGkgXHUyMjY2IE4pIFx1MzA2Ylx1MzA2Zlx1ZmYwY1x1NjU3NFx1NjU3MCBBPHN1Yj5pPFwvc3ViPiBcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwNmZcdWZmMGNcdTMwYWFcdTMwZWNcdTMwZjNcdTMwYjggaSBcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNTVcdTMwNGMgQTxzdWI+aTxcL3N1Yj4gXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxZmFcdTUyOWJcdTMwNmJcdWZmMGNcdTdiYjFcdThhNzBcdTMwODFcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmVcdTdkY2ZcdTU0OGNcdTMwNmVcdTY3MDBcdTVjMGZcdTUwMjRcdTMwOTIgMSBcdTg4NGNcdTMwNjdcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJKYXBhbmVzZSIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xIFx1MjI2NiBOIFx1MjI2NiAyMCAwMDBcdWZmMGU8XC9saT5cclxuXHQ8bGk+MSBcdTIyNjYgTSBcdTIyNjYgMSAwMDBcdWZmMGU8XC9saT5cclxuXHQ8bGk+MCBcdTIyNjYgSyBcdTIyNjYgMSAwMDAgMDAwIDAwMFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4xIFx1MjI2NiBBPHN1Yj5pPFwvc3ViPiBcdTIyNjYgMSAwMDAgMDAwIDAwMCAoMSBcdTIyNjYgaSBcdTIyNjYgTilcdWZmMGU8XC9saT5cclxuXHQ8bGk+TSBcdTIyNjYgTlx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD5OICZsZTsgMjAuPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD5OIFx1MjI2NiAyIDAwMCwmbmJzcDtNIFx1MjI2NiAxMDAuPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5cdThmZmRcdTUyYTBcdTMwNmVcdTUyMzZcdTk2NTBcdTMwNmZcdTMwNmFcdTMwNDRcdWZmMGU8XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+MSBcdTc1NmFcdTc2ZWVcdTMwNmVcdTdiYjFcdTMwNmJcdTMwYWFcdTMwZWNcdTMwZjNcdTMwYjggMSBcdTMwNGJcdTMwODlcdTMwYWFcdTMwZWNcdTMwZjNcdTMwYjggMyBcdTMwN2VcdTMwNjdcdTMwNmUgMyBcdTUwMGJcdTMwNmVcdTMwYWFcdTMwZWNcdTMwZjNcdTMwYjhcdTMwOTJcdThhNzBcdTMwODFcdWZmMGMyIFx1NzU2YVx1NzZlZVx1MzA2ZVx1N2JiMVx1MzA2Ylx1MzBhYVx1MzBlY1x1MzBmM1x1MzBiOCA0IFx1MzA0Ylx1MzA4OVx1MzBhYVx1MzBlYyBcdTMwZjNcdTMwYjggNiBcdTMwN2VcdTMwNjdcdTMwNmUgMyBcdTUwMGJcdTMwNmVcdTMwYWFcdTMwZWNcdTMwZjNcdTMwYjhcdTMwOTJcdThhNzBcdTMwODFcdTMwOGJcdTMwNjhcdWZmMGNcdTdiYjFcdThhNzBcdTMwODFcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmVcdTdkY2ZcdTU0OGNcdTMwNmYgKDYrMyZ0aW1lczsoMyZtaW51czsxKSkrKDYrMyZ0aW1lczsoMiZtaW51czsxKSkgPSAyMSBcdTMwNjhcdTMwNmFcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHUzMDY5XHUzMDZlXHUzMDg4XHUzMDQ2XHUzMDZiXHU4YTcwXHUzMDgxXHUzMDY2XHUzMDgyXHU3YmIxXHU4YTcwXHUzMDgxXHUzMDZiXHUzMDRiXHUzMDRiXHUzMDhiXHUzMGIzXHUzMGI5XHUzMGM4XHUzMDZlXHU3ZGNmXHU1NDhjXHUzMDRjIDIxIFx1MzA5Mlx1NGUwYlx1NTZkZVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2YVx1MzA0NFx1MzA2ZVx1MzA2N1x1ZmYwYzIxIFx1MzA5Mlx1NTFmYVx1NTI5Ylx1MzA1OVx1MzA4Ylx1ZmYwZTxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD4xMSBcdTUwMGJcdTMwNmVcdTdiYjFcdTMwOTJcdTc1MjhcdTYxMGZcdTMwNTdcdTMwNjZcdWZmMGNcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTMwNmVcdTdiYjFcdTMwNmJcdTUyNGRcdTMwNGJcdTMwODlcdTk4MDZcdTMwNmIgMSBcdTUwMGJcdWZmMGMzIFx1NTAwYlx1ZmYwYzEgXHU1MDBiXHVmZjBjMSBcdTUwMGJcdWZmMGMzIFx1NTAwYlx1ZmYwYzEgXHU1MDBiXHVmZjBjMSBcdTUwMGJcdWZmMGMyIFx1NTAwYlx1ZmYwYzEgXHU1MDBiXHVmZjBjIDEgXHU1MDBiXHVmZjBjMSBcdTUwMGJcdTMwNmVcdTMwYWFcdTMwZWNcdTMwZjNcdTMwYjhcdTMwOTJcdThhNzBcdTMwODFcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNjdcdWZmMGNcdTdiYjFcdThhNzBcdTMwODFcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmVcdTdkY2ZcdTU0OGNcdTMwNGNcdTY3MDBcdTVjMGZcdTMwNjhcdTMwNmFcdTMwOGJcdWZmMGU8XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl80IjoiPHA+XHU3YjU0XHUzMDQ4XHUzMDRjIDMyIFx1MzBkM1x1MzBjM1x1MzBjOFx1N2IyNlx1NTNmN1x1NGVkOFx1MzA0ZFx1NjU3NFx1NjU3MFx1MzA2ZVx1N2JjNFx1NTZmMlx1MzA2Ylx1NTNjZVx1MzA3ZVx1MzA4Ylx1MzA2OFx1MzA2Zlx1OTY1MFx1MzA4OVx1MzA2YVx1MzA0NFx1MzA1M1x1MzA2OFx1MzA2Ylx1NmNlOFx1NjEwZlx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiJ9XQ==

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2015/2016 1번

  • 문제의 오타를 찾은 사람: khj94811
  • 문제를 번역한 사람: KimJJ

채점 및 기타 정보

  • 예제는 채점하지 않는다.