시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 586 116 90 22.670%

문제

수아는 x축 위에 앉아있다. "나는 x축이 너무 좋아!!" 라고 수아가 말했다. 수평선에는 n개의 사탕바구니가 있고, 각 사탕 바구니에는 m개의 사탕이 있다. 각 사탕 바구니는 x1, x2, ..., xn 에 있고, 수아는 0에 있다.

오늘은 날씨가 덥다. 따라서, 시간이 1만큼 지날 때 마다, 모든 사탕바구니에서 사탕은 1만큼 줄어든다. 수아는 매우 배가고프기 때문에, 사탕바구니에 있는 사탕을 0만에 모두 먹을 수 있다. 수아가 1만큼 움직일 때, 시간은 1만큼 지나간다.

수아가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n과 m이 주어진다. 둘째 줄부터 n개의 줄에 사탕 바구니의 위치 xi가 주어진다. (0<=n<=300, 1<=m<=1,000,000, -10,000<=xi<=10,000) 사탕 바구니의 위치는 중복되지 않는다.

출력

수아가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력 1

3 15
6
-3
1

예제 출력 1

25

힌트

W3sicHJvYmxlbV9pZCI6IjI0MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWMyMThcdWM1NDRcdWQwZDUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIxOFx1YzU0NFx1YjI5NCB4XHVjZDk1IFx1YzcwNFx1YzVkMCBcdWM1NDlcdWM1NDRcdWM3ODhcdWIyZTQuICZxdW90O1x1YjA5OFx1YjI5NCB4XHVjZDk1XHVjNzc0IFx1YjEwOFx1YmIzNCBcdWM4OGJcdWM1NDQhISZxdW90OyBcdWI3N2NcdWFjZTAgXHVjMjE4XHVjNTQ0XHVhYzAwIFx1YjlkMFx1ZDU4OFx1YjJlNC4gXHVjMjE4XHVkM2M5XHVjMTIwXHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjMGFjXHVkMGQ1XHViYzE0XHVhZDZjXHViMmM4XHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YzBhY1x1ZDBkNSBcdWJjMTRcdWFkNmNcdWIyYzhcdWM1ZDBcdWIyOTQgbVx1YWMxY1x1Yzc1OCBcdWMwYWNcdWQwZDVcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjMGFjXHVkMGQ1IFx1YmMxNFx1YWQ2Y1x1YjJjOFx1YjI5NCB4PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIC4uLiwgeDxzdWI+bjxcL3N1Yj4gXHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHVjMjE4XHVjNTQ0XHViMjk0IDBcdWM1ZDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MjRcdWIyOThcdWM3NDAgXHViMGEwXHVjNTI4XHVhYzAwIFx1YjM2NVx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWMyZGNcdWFjMDRcdWM3NzQgMVx1YjljY1x1ZDA3YyBcdWM5YzBcdWIwYTAgXHViNTRjIFx1YjljOFx1YjJlNCwgXHViYWE4XHViNGUwIFx1YzBhY1x1ZDBkNVx1YmMxNFx1YWQ2Y1x1YjJjOFx1YzVkMFx1YzExYyBcdWMwYWNcdWQwZDVcdWM3NDAgMVx1YjljY1x1ZDA3YyBcdWM5MDRcdWM1YjRcdWI0ZTBcdWIyZTQuIFx1YzIxOFx1YzU0NFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHViYzMwXHVhYzAwXHVhY2UwXHVkNTA0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMGFjXHVkMGQ1XHViYzE0XHVhZDZjXHViMmM4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NDQgMFx1YjljY1x1YzVkMCBcdWJhYThcdWI0NTAgXHViYTM5XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzIxOFx1YzU0NFx1YWMwMCAxXHViOWNjXHVkMDdjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWI1NGMsIFx1YzJkY1x1YWMwNFx1Yzc0MCAxXHViOWNjXHVkMDdjIFx1YzljMFx1YjA5OFx1YWMwNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjNTQ0XHVhYzAwIFx1YmEzOVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVhY2ZjIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzBhY1x1ZDBkNSBcdWJjMTRcdWFkNmNcdWIyYzhcdWM3NTggXHVjNzA0XHVjZTU4IHg8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAmbHQ7PW4mbHQ7PTMwMCwgMSZsdDs9bSZsdDs9MSwwMDAsMDAwLCAtMTAsMDAwJmx0Oz14aSZsdDs9MTAsMDAwKSBcdWMwYWNcdWQwZDUgXHViYzE0XHVhZDZjXHViMmM4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWM5MTFcdWJjZjVcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzIxOFx1YzU0NFx1YWMwMCBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQxOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlZXRsZSIsImRlc2NyaXB0aW9uIjoiPHA+QSBiZWV0bGUgXHVmYjAxbmRzIGl0c2VsZiBvbiBhIHRoaW4gaG9yaXpvbnRhbCBicmFuY2guICZsZHF1bztIZXJlIEkgYW0gb24gYSB0aGluIGhvcml6b250YWwgYnJhbmNoLCZyZHF1bzsgdGhpbmtzIHRoZSBiZWV0bGUsICZsZHF1bztJIGZlZWwgcHJldHR5IG11Y2ggbGlrZSBvbiBhbiB4LWF4aXMhJnJkcXVvOyBJdCBzdXJlbHkgaXMgYSBiZWV0bGUgb2YgZGVlcCBtYXRoZW1hdGljYWwgdGhvdWdodC48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIGFsc28gbiBkcm9wcyBvZiBkZXcgb24gdGhhdCBzYW1lIGJyYW5jaCwgZWFjaCBob2xkaW5nIG0gdW5pdHMgb2Ygd2F0ZXIuIFRoZWlyIGJlZXRsZSZuZGFzaDtiYXNlZCBpbnRlZ2VyIGNvb3JkaW5hdGVzIGFyZSB4PHN1Yj4xPFwvc3ViPix4PHN1Yj4yPFwvc3ViPiwuLi4gLHg8c3ViPm48XC9zdWI+LjxcL3A+XHJcblxyXG48cD5JdCBpcyBjbGVhciB0aGF0IHRoZSBkYXkgd2lsbCBiZSBob3QuIEFscmVhZHkgaW4gb25lIHVuaXQgb2YgdGltZSBvbmUgdW5pdCBvZiB3YXRlciBnb2VzIGF3YXkgZnJvbSBlYWNoIGRyb3AuIFRoZSBiZWV0bGUgaXMgdGhpcnN0eS4gSXQgaXMgc28gdGhpcnN0eSB0aGF0IGlmIGl0IHJlYWNoZWQgYSBkcm9wIG9mIGRldyBpdCB3b3VsZCBkcmluayBpdCBpbiB6ZXJvIHRpbWUuIEluIG9uZSB1bml0IG9mIHRpbWUgdGhlIGJlZXRsZSBjYW4gY3Jhd2wgb25lIHVuaXQgb2YgbGVuZ3RoLiBCdXQgd291bGQgYWxsIHRoaXMgY3Jhd2xpbmcgcGF5IG9mZj8gVGhhdCZyc3F1bztzIHdoYXQgYnV6emVzIHRoZSBiZWV0bGUuPFwvcD5cclxuXHJcbjxwPlNvIHlvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHdoaWNoLCBnaXZlbiBjb29yZGluYXRlcyBvZiBkZXcgZHJvcHMsIGNhbGN1bGF0ZXMgdGhlIG1heGltYWwgYW1vdW50IG9mIHdhdGVyIHRoZSBiZWV0bGUgY2FuIHBvc3NpYmx5IGRyaW5rLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIFx1ZmIwMXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBuIGFuZCBtLiBUaGUgbmV4dCBuIGxpbmVzIGNvbnRhaW4gaW50ZWdlciBjb29yZGluYXRlcyB4PHN1Yj4xPFwvc3ViPix4PHN1Yj4yPFwvc3ViPiwuLi4gLHg8c3ViPm48XC9zdWI+LjxcL3A+XHJcblxyXG48cD4wICZsZTsgbiAmbGU7IDMwMCwgMSAmbGU7IG0gJmxlOyAxLDAwMCwwMDAsICZtaW51czsxMCwwMDAgJmxlOyB4PHN1Yj4xPFwvc3ViPix4PHN1Yj4yPFwvc3ViPiwuLi4gLHg8c3ViPm48XC9zdWI+ICZsZTsgMTAsMDAwLHg8c3ViPmk8XC9zdWI+ICZuZTsgeDxzdWI+ajxcL3N1Yj4gZm9yIGkgJm5lOyBqLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBwcm9ncmFtIHNob3VsZCB3cml0ZSBvbmUgbGluZSB0byBzdGFuZGFyZCBvdXRwdXQgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyOiB0aGUgbWF4aW1hbCBhbW91bnQgb2Ygd2F0ZXIgdGhlIGJlZXRsZSBjYW4gcG9zc2libHkgZHJpbmsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 1번