홀딩

Ivica와 그의 홀딩, 즉 그가 소유한 크로아티아의 N개 기업에 어려운 시기가 다가온다. 각 기업은 모두 부채를 지고 있어, 정부는 변호사들을 보내 그에게서 모든 것을 빼앗으려 한다. 하지만 Ivica가 막대한 부채에도 불구하고 일부 기업을 남겨 두기로 정부와 합의했다는 사실을 우리는 단독으로 알아냈다. 어떤 기업인지는 우리도 알아냈다.

정부 변호사들은 Ivica의 기업에 대한 N장의 문서를 탁자 위에 펼쳐 두었다. 첫 번째 기업의 부채는 첫 번째 문서 A1에, 두 번째 기업의 부채는 A2에, ..., 마지막 기업의 부채는 마지막 문서 AN에 적혀 있다. Ivica는 기업 AL, AL+1, ..., AR을 계속 소유하도록 정부와 합의했다. 여기서 L과 R은 탁자 위 문서 배열에서의 위치를 나타낸다. Ivica에게 다행스럽게도, 변호사들도 (역시나) 부패했다. 그들은 Ivica에게 합의한 것과 같은 연속된 부분 배열(L번째 문서부터 R번째 문서까지)을 받도록 강제하지만, 특정 비용을 받고 탁자 위의 두 문서를 서로 바꾸게 허용해 준다. 더 정확히는, 위치 i와 j에 있는 문서를 바꾸는 비용은 |i − j| 쿠나(크로아티아 화폐)이다. Ivica는 절박하다. 주머니에는 K 쿠나밖에 없고, 이 돈을 잘 써서 자신이 남게 되는 기업들의 부채 합이 최대한 작아지기를 바란다.

Ivica가 목표를 달성하도록 도와주자.

첫 번째 줄에는 문제 설명에 나오는 네 정수 N, L, R (1 ≤ L ≤ R ≤ N ≤ 100)과 K (0 ≤ K ≤ 10 000)가 공백으로 구분되어 주어진다.

두 번째 줄에는 문제 설명에 나오는 N개의 정수 Ai (0 ≤ Ai ≤ 106)가 주어진다.

Ivica가 K 쿠나를 최적으로 사용했을 때, 그가 지게 되는 총 부채의 최솟값을 나타내는 정수를 하나 출력한다.