시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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에 문제를 해결할 수 있으며 이것이 최소다.

W3sicHJvYmxlbV9pZCI6IjYxMzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWQ2NTRcdWMxMjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBCT0pcdWM3NTggXHVjODA0XHVkNjU0XHVjMTIwXHVjNzQ0IFx1YWNmNVx1YzBhY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkJPSlx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzgwNFx1YzJlMFx1YzhmY1x1YWMwMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMSBcdWM4MDRcdWMyZTBcdWM4ZmNcdWIyOTQgSGkgXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWFjMDBcdWM5YzRcdWIyZTQuIFx1YzgwNFx1ZDY1NFx1YzEyMFx1Yzc0MCAxLDIuLi5OIFx1YmM4OCBcdWM4MDRcdWMyZTBcdWM4ZmNcdWM1ZDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzEyNFx1Y2U1OFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1Yzc3NFx1YjU0YyBDICogfFx1YjQ1MCBcdWM4MDRcdWMyZTBcdWM4ZmNcdWM3NTggXHViMTkyXHVjNzc0IFx1Y2MyOHwgXHViOWNjXHVkMDdjXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWI2MTBcdWQ1NWMgXHVjODA0XHVjMmUwXHVjOGZjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWIxOTJcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzgwNFx1YzJlMFx1YzhmY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgWFx1YjljY1x1ZDA3YyBcdWIxOTJcdWM2MDBcdWIyZTRcdWJhNzQsIFheMiBcdWI5Y2NcdWQwN2NcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzc0IFx1YjRlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWM4MDRcdWMyZTBcdWM4ZmNcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIFx1YjE5Mlx1Yzc3NFx1YWNlMCBcdWM4MDRcdWQ2NTRcdWMxMjBcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTc0XHVjMTFjIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3M2NcdWI4NWMgXHVjODA0XHVkNjU0XHVjMTIwXHVjNzQ0IFx1YWNmNVx1YzBhY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVjODA0XHVkNjU0XHVjMTIwXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmx0Oz0gTiAmbHQ7PSAxMDAsMDAwLCAxICZsdDs9IEMgJmx0Oz0gMTAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgSGlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbHQ7PSBIaSAmbHQ7PSAxMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjN2FjXHVkNjA0XHVjNzc0XHVhYzAwIFx1YzgwNFx1ZDY1NFx1YzEyMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWIyOTQgXHViMzcwIFx1YjRkY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+WzMsIDMsIDUsIDMsIDRdIFx1Yjg1YyBcdWM4MDRcdWMyZTBcdWM4ZmNcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIFx1YmMxNFx1YWZiOFx1YmE3NCAxNVx1YzVkMCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNTc0XHVhY2IwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVjNzc0XHVhYzgzXHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYxMzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUZWxlcGhvbmUgV2lyZSIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4mIzM5O3MgY293cyBhcmUgZ2V0dGluZyByZXN0bGVzcyBhYm91dCB0aGVpciBwb29yIHRlbGVwaG9uZSBzZXJ2aWNlOyB0aGV5IHdhbnQgRkogdG8gcmVwbGFjZSB0aGUgb2xkIHRlbGVwaG9uZSB3aXJlIHdpdGggbmV3LCBtb3JlIGVmZmljaWVudCB3aXJlLiBUaGUgbmV3IHdpcmluZyB3aWxsIHV0aWxpemUgTiAoMiAmbHQ7PSBOICZsdDs9IDEwMCwwMDApIGFscmVhZHktaW5zdGFsbGVkIHRlbGVwaG9uZSBwb2xlcywgZWFjaCB3aXRoIHNvbWUgaGVpZ2h0X2kgbWV0ZXJzICgxICZsdDs9IGhlaWdodF9pICZsdDs9IDEwMCkuIFRoZSBuZXcgd2lyZSB3aWxsIGNvbm5lY3QgdGhlIHRvcHMgb2YgZWFjaCBwYWlyIG9mIGFkamFjZW50IHBvbGVzIGFuZCB3aWxsIGluY3VyIGEgcGVuYWx0eSBjb3N0IEMgKiB0aGUgdHdvIHBvbGVzJiMzOTsgaGVpZ2h0IGRpZmZlcmVuY2UgZm9yIGVhY2ggc2VjdGlvbiBvZiB3aXJlIHdoZXJlIHRoZSBwb2xlcyBhcmUgb2YgZGlmZmVyZW50IGhlaWdodHMgKDEgJmx0Oz0gQyAmbHQ7PSAxMDApLiBUaGUgcG9sZXMsIG9mIGNvdXJzZSwgYXJlIGluIGEgY2VydGFpbiBzZXF1ZW5jZSBhbmQgY2FuIG5vdCBiZSBtb3ZlZC48XC9wPlxyXG5cclxuPHA+RmFybWVyIEpvaG4gZmlndXJlcyB0aGF0IGlmIGhlIG1ha2VzIHNvbWUgcG9sZXMgdGFsbGVyIGhlIGNhbiByZWR1Y2UgaGlzIHBlbmFsdGllcywgdGhvdWdoIHdpdGggc29tZSBvdGhlciBhZGRpdGlvbmFsIGNvc3QuIEhlIGNhbiBhZGQgYW4gaW50ZWdlciBYIG51bWJlciBvZiBtZXRlcnMgdG8gYSBwb2xlIGF0IGEgY29zdCBvZiBYXjIuPFwvcD5cclxuXHJcbjxwPkhlbHAgRmFybWVyIEpvaG4gZGV0ZXJtaW5lIHRoZSBjaGVhcGVzdCBjb21iaW5hdGlvbiBvZiBncm93aW5nIHBvbGUgaGVpZ2h0cyBhbmQgY29ubmVjdGluZyB3aXJlIHNvIHRoYXQgdGhlIGNvd3MgY2FuIGdldCB0aGVpciBuZXcgYW5kIGltcHJvdmVkIHNlcnZpY2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgQzxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXI6IGhlaWdodF9pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRoZSBtaW5pbXVtIHRvdGFsIGFtb3VudCBvZiBtb25leSB0aGF0IGl0IHdpbGwgY29zdCBGYXJtZXIgSm9obiB0byBhdHRhY2ggdGhlIG5ldyB0ZWxlcGhvbmUgd2lyZS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5UaGVyZSBhcmUgNSB0ZWxlcGhvbmUgcG9sZXMsIGFuZCB0aGUgdmVydGljYWwgZGlzdGFuY2UgcGVuYWx0eSBpcyAkMlwvbWV0ZXIuIFRoZSBwb2xlcyBpbml0aWFsbHkgaGF2ZSBoZWlnaHRzIG9mIDIsIDMsIDUsIDEsIGFuZCA0LCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPlRoZSBiZXN0IHdheSBpcyBmb3IgRmFybWVyIEpvaG4gdG8gcmFpc2UgdGhlIGZpcnN0IHBvbGUgYnkgMSB1bml0IGFuZCB0aGUgZm91cnRoIHBvbGUgYnkgMiB1bml0cywgbWFraW5nIHRoZSBoZWlnaHRzIChpbiBvcmRlcikgMywgMywgNSwgMywgYW5kIDQuIFRoaXMgY29zdHMgJDUuIFRoZSByZW1haW5pbmcgd2lyaW5nIHdpbGwgY29zdCAkMiooMCsyKzIrMSkgPSAkMTAsIGZvciBhIHRvdGFsIG9mICQxNS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==