문제

2차원 세계를 지배하는 J. 왕국에 왕세자 H. 가 태어났습니다! 국왕인 M. 은 이를 기념하여 2주일간의 축제기간을 선포했습니다. 탄생 축제기간의 마지막 날에는 거대한 축포를 쏘아올려 J. 왕국의 모든 국민들이 그 축포를 볼 수 있도록 할 것입니다.

하지만 정작 축포를 발사할 전날이 되자, 국왕인 M. 은 고민이 생겼습니다. 그 고민의 원인은 다름이 아니라 J. 왕국의 위에 떠있는 수많은 구름들 때문입니다. 축포가 구름에 가려서 안 보이기라도 하면 불운의 조짐으로 여겨질 것이며 축제를 위해 수도를 찾은 사람들이 크게 실망할 것입니다.

고민 끝에 M. 왕은 대학생 시절에 자취방 제습제 대용으로 만들었던 “Nerdull-Nerdull-Han 레이저포(이하 너덜포)”를 꺼냈습니다. 희귀 금속인 Nerdull로 만든 너덜포는 고출력의 매우 뜨거운 광선을 발사하기 때문에 수증기 덩어리인 구름따위는 스치기만 해도 사라져 버립니다 (하지만 맞지 않으면 아무 것도 아니라는 사실에 주의하세요.) M. 은 이 문제를 다음과 같이 단순화할 수 있다는 것을 직감했습니다:

1. 하늘에 존재하는 N개의 구름은 x축에 평행한 선분이다. 모든 구름은 x > 0인 영역에 존재한다.
2. 지면은 y = 0인 직선으로 생각하며, 너덜포는 지면 위의 한 지점으로부터 연직 상방으로 발사한다.
3. 내구도의 문제 때문에 너덜포는 최대 K회까지만 발사가 가능하다.
4. 너덜포를 발사하면 고출력 광선을 따라 그 위에 존재하는 모든 구름이 사라진다. 이 때의 필요한 전기 비용은 다음과 같다: [ 너덜포의 x 좌표값(= 발전소로부터 전력을 끌어오는 비용) ] * [사라지는 구름의 수]

M. 은 이 문제를 쉽게 풀수 있다는 것을 직감했지만, 암산 도중에 H. 가 울기 시작했기 때문에 당신에게 계산을 맡겼습니다. J. 왕국은 축제 기간동안 예산을 많이 사용하였기 때문에 구름을 제거하는 비용은 가능한 최소로 줄이고 싶어합니다. 가능한 적은 예산을 계산해서 M. 국왕 전하의 신임을 얻으세요.

모든 구름을 제거하는 일이 불가능한 경우는 없습니다. 왕세자 H. 는 신의 축복 아래서 태어났거든요!