시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 36 21 16 51.613%

문제

재현이는 BOJ의 전화선을 공사하려고 한다.

BOJ에는 N개의 전신주가 있으며, 각 전신주는 Hi 의 높이를 가진다. 전화선은 1,2...N 번 전신주에 순서대로 설치되어야 하며, 이 때 C * |두 전신주의 높이 차| 만큼의 비용이 든다.

재현이는 또한 전신주의 높이를 높일 수 있다. 만약 전신주의 높이를 X만큼 높였다면, X^2 만큼의 비용이 든다.

재현이는 적절히 전신주의 높이를 높이고 전화선을 설치해서 최소 비용으로 전화선을 공사하려고 한다. 재현이를 도와 전화선을 설치하는 최소 비용을 출력하라.

입력

첫째 줄에 N과 C가 주어진다. (1 <= N <= 100,000, 1 <= C <= 100)

이후 N개의 줄에 Hi가 주어진다. (1 <= Hi <= 100)

출력

재현이가 전화선을 설치하는 데 드는 최소 비용을 출력하라.

예제 입력 1

5 2
2
3
5
1
4

예제 출력 1

15

힌트

[3, 3, 5, 3, 4] 로 전신주의 높이를 바꾸면 15에 문제를 해결할 수 있으며 이것이 최소다.

W3sicHJvYmxlbV9pZCI6IjYxMzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWQ2NTRcdWMxMjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBCT0pcdWM3NTggXHVjODA0XHVkNjU0XHVjMTIwXHVjNzQ0IFx1YWNmNVx1YzBhY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkJPSlx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzgwNFx1YzJlMFx1YzhmY1x1YWMwMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMSBcdWM4MDRcdWMyZTBcdWM4ZmNcdWIyOTQgSGkgXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWFjMDBcdWM5YzRcdWIyZTQuIFx1YzgwNFx1ZDY1NFx1YzEyMFx1Yzc0MCAxLDIuLi5OIFx1YmM4OCBcdWM4MDRcdWMyZTBcdWM4ZmNcdWM1ZDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzEyNFx1Y2U1OFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1Yzc3NCBcdWI1NGMgQyAqIHxcdWI0NTAgXHVjODA0XHVjMmUwXHVjOGZjXHVjNzU4IFx1YjE5Mlx1Yzc3NCBcdWNjMjh8IFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NzQgXHViNGUwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHViNjEwXHVkNTVjIFx1YzgwNFx1YzJlMFx1YzhmY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHViMTkyXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM4MDRcdWMyZTBcdWM4ZmNcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIFhcdWI5Y2NcdWQwN2MgXHViMTkyXHVjNjAwXHViMmU0XHViYTc0LCBYXjIgXHViOWNjXHVkMDdjXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVjODA0XHVjMmUwXHVjOGZjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWIxOTJcdWM3NzRcdWFjZTAgXHVjODA0XHVkNjU0XHVjMTIwXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU3NFx1YzExYyBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzNjXHViODVjIFx1YzgwNFx1ZDY1NFx1YzEyMFx1Yzc0NCBcdWFjZjVcdWMwYWNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3YWNcdWQ2MDRcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YzgwNFx1ZDY1NFx1YzEyMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsdDs9IE4gJmx0Oz0gMTAwLDAwMCwgMSAmbHQ7PSBDICZsdDs9IDEwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIEhpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmx0Oz0gSGkgJmx0Oz0gMTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YWMwMCBcdWM4MDRcdWQ2NTRcdWMxMjBcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTU4XHViMjk0IFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlszLCAzLCA1LCAzLCA0XSBcdWI4NWMgXHVjODA0XHVjMmUwXHVjOGZjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWJjMTRcdWFmYjhcdWJhNzQgMTVcdWM1ZDAgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwIFx1Yzc3NFx1YWM4M1x1Yzc3NCBcdWNkNWNcdWMxOGNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2MTMyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGVsZXBob25lIFdpcmUiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huJiMzOTtzIGNvd3MgYXJlIGdldHRpbmcgcmVzdGxlc3MgYWJvdXQgdGhlaXIgcG9vciB0ZWxlcGhvbmUgc2VydmljZTsgdGhleSB3YW50IEZKIHRvIHJlcGxhY2UgdGhlIG9sZCB0ZWxlcGhvbmUgd2lyZSB3aXRoIG5ldywgbW9yZSBlZmZpY2llbnQgd2lyZS4gVGhlIG5ldyB3aXJpbmcgd2lsbCB1dGlsaXplIE4gKDIgJmx0Oz0gTiAmbHQ7PSAxMDAsMDAwKSBhbHJlYWR5LWluc3RhbGxlZCB0ZWxlcGhvbmUgcG9sZXMsIGVhY2ggd2l0aCBzb21lIGhlaWdodF9pIG1ldGVycyAoMSAmbHQ7PSBoZWlnaHRfaSAmbHQ7PSAxMDApLiBUaGUgbmV3IHdpcmUgd2lsbCBjb25uZWN0IHRoZSB0b3BzIG9mIGVhY2ggcGFpciBvZiBhZGphY2VudCBwb2xlcyBhbmQgd2lsbCBpbmN1ciBhIHBlbmFsdHkgY29zdCBDICogdGhlIHR3byBwb2xlcyYjMzk7IGhlaWdodCBkaWZmZXJlbmNlIGZvciBlYWNoIHNlY3Rpb24gb2Ygd2lyZSB3aGVyZSB0aGUgcG9sZXMgYXJlIG9mIGRpZmZlcmVudCBoZWlnaHRzICgxICZsdDs9IEMgJmx0Oz0gMTAwKS4gVGhlIHBvbGVzLCBvZiBjb3Vyc2UsIGFyZSBpbiBhIGNlcnRhaW4gc2VxdWVuY2UgYW5kIGNhbiBub3QgYmUgbW92ZWQuPFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIGZpZ3VyZXMgdGhhdCBpZiBoZSBtYWtlcyBzb21lIHBvbGVzIHRhbGxlciBoZSBjYW4gcmVkdWNlIGhpcyBwZW5hbHRpZXMsIHRob3VnaCB3aXRoIHNvbWUgb3RoZXIgYWRkaXRpb25hbCBjb3N0LiBIZSBjYW4gYWRkIGFuIGludGVnZXIgWCBudW1iZXIgb2YgbWV0ZXJzIHRvIGEgcG9sZSBhdCBhIGNvc3Qgb2YgWF4yLjxcL3A+XHJcblxyXG48cD5IZWxwIEZhcm1lciBKb2huIGRldGVybWluZSB0aGUgY2hlYXBlc3QgY29tYmluYXRpb24gb2YgZ3Jvd2luZyBwb2xlIGhlaWdodHMgYW5kIGNvbm5lY3Rpbmcgd2lyZSBzbyB0aGF0IHRoZSBjb3dzIGNhbiBnZXQgdGhlaXIgbmV3IGFuZCBpbXByb3ZlZCBzZXJ2aWNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIEM8XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyOiBoZWlnaHRfaTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgbWluaW11bSB0b3RhbCBhbW91bnQgb2YgbW9uZXkgdGhhdCBpdCB3aWxsIGNvc3QgRmFybWVyIEpvaG4gdG8gYXR0YWNoIHRoZSBuZXcgdGVsZXBob25lIHdpcmUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHA+VGhlcmUgYXJlIDUgdGVsZXBob25lIHBvbGVzLCBhbmQgdGhlIHZlcnRpY2FsIGRpc3RhbmNlIHBlbmFsdHkgaXMgJDJcL21ldGVyLiBUaGUgcG9sZXMgaW5pdGlhbGx5IGhhdmUgaGVpZ2h0cyBvZiAyLCAzLCA1LCAxLCBhbmQgNCwgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5UaGUgYmVzdCB3YXkgaXMgZm9yIEZhcm1lciBKb2huIHRvIHJhaXNlIHRoZSBmaXJzdCBwb2xlIGJ5IDEgdW5pdCBhbmQgdGhlIGZvdXJ0aCBwb2xlIGJ5IDIgdW5pdHMsIG1ha2luZyB0aGUgaGVpZ2h0cyAoaW4gb3JkZXIpIDMsIDMsIDUsIDMsIGFuZCA0LiBUaGlzIGNvc3RzICQ1LiBUaGUgcmVtYWluaW5nIHdpcmluZyB3aWxsIGNvc3QgJDIqKDArMisyKzEpID0gJDEwLCBmb3IgYSB0b3RhbCBvZiAkMTUuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=