시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1367 387 300 29.970%

문제

수아는 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+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBuICZsZTsgMzAwLCAxICZsZTsgbSAmbGU7IDEsMDAwLDAwMCwgLTEwLDAwMCAmbGU7IHg8c3ViPmk8XC9zdWI+ICZsZTsgMTAsMDAwKSBcdWMwYWNcdWQwZDUgXHViYzE0XHVhZDZjXHViMmM4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWM5MTFcdWJjZjVcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzIxOFx1YzU0NFx1YWMwMCBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjQxOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlZXRsZSIsImRlc2NyaXB0aW9uIjoiPHA+QSBiZWV0bGUgXHVmYjAxbmRzIGl0c2VsZiBvbiBhIHRoaW4gaG9yaXpvbnRhbCBicmFuY2guICZsZHF1bztIZXJlIEkgYW0gb24gYSB0aGluIGhvcml6b250YWwgYnJhbmNoLCZyZHF1bzsgdGhpbmtzIHRoZSBiZWV0bGUsICZsZHF1bztJIGZlZWwgcHJldHR5IG11Y2ggbGlrZSBvbiBhbiB4LWF4aXMhJnJkcXVvOyBJdCBzdXJlbHkgaXMgYSBiZWV0bGUgb2YgZGVlcCBtYXRoZW1hdGljYWwgdGhvdWdodC48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIGFsc28gbiBkcm9wcyBvZiBkZXcgb24gdGhhdCBzYW1lIGJyYW5jaCwgZWFjaCBob2xkaW5nIG0gdW5pdHMgb2Ygd2F0ZXIuIFRoZWlyIGJlZXRsZSZuZGFzaDtiYXNlZCBpbnRlZ2VyIGNvb3JkaW5hdGVzIGFyZSB4PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIC4uLiwgeDxzdWI+bjxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPkl0IGlzIGNsZWFyIHRoYXQgdGhlIGRheSB3aWxsIGJlIGhvdC4gQWxyZWFkeSBpbiBvbmUgdW5pdCBvZiB0aW1lIG9uZSB1bml0IG9mIHdhdGVyIGdvZXMgYXdheSBmcm9tIGVhY2ggZHJvcC4gVGhlIGJlZXRsZSBpcyB0aGlyc3R5LiBJdCBpcyBzbyB0aGlyc3R5IHRoYXQgaWYgaXQgcmVhY2hlZCBhIGRyb3Agb2YgZGV3IGl0IHdvdWxkIGRyaW5rIGl0IGluIHplcm8gdGltZS4gSW4gb25lIHVuaXQgb2YgdGltZSB0aGUgYmVldGxlIGNhbiBjcmF3bCBvbmUgdW5pdCBvZiBsZW5ndGguIEJ1dCB3b3VsZCBhbGwgdGhpcyBjcmF3bGluZyBwYXkgb2ZmPyBUaGF0JnJzcXVvO3Mgd2hhdCBidXp6ZXMgdGhlIGJlZXRsZS48XC9wPlxyXG5cclxuPHA+U28geW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gd2hpY2gsIGdpdmVuIGNvb3JkaW5hdGVzIG9mIGRldyBkcm9wcywgY2FsY3VsYXRlcyB0aGUgbWF4aW1hbCBhbW91bnQgb2Ygd2F0ZXIgdGhlIGJlZXRsZSBjYW4gcG9zc2libHkgZHJpbmsuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIG4gYW5kIG0uIFRoZSBuZXh0IG4gbGluZXMgY29udGFpbiBpbnRlZ2VyIGNvb3JkaW5hdGVzIHg8c3ViPjE8XC9zdWI+LCB4PHN1Yj4yPFwvc3ViPiwgLi4uLCB4PHN1Yj5uPFwvc3ViPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgcHJvZ3JhbSBzaG91bGQgd3JpdGUgb25lIGxpbmUgdG8gc3RhbmRhcmQgb3V0cHV0IGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlcjogdGhlIG1heGltYWwgYW1vdW50IG9mIHdhdGVyIHRoZSBiZWV0bGUgY2FuIHBvc3NpYmx5IGRyaW5rLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MCAmbGU7IG4gJmxlOyAzMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IG0gJmxlOyAxLDAwMCwwMDA8XC9saT5cclxuXHQ8bGk+Jm1pbnVzOzEwLDAwMCAmbGU7IHg8c3ViPjE8XC9zdWI+LCB4PHN1Yj4yPFwvc3ViPiwgLi4uLCB4PHN1Yj5uPFwvc3ViPiAmbGU7IDEwLDAwMDxcL2xpPlxyXG5cdDxsaT54PHN1Yj5pPFwvc3ViPiAmbmU7IHg8c3ViPmo8XC9zdWI+IGZvciBpICZuZTsgai48XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 1번