곧 졸업을 앞두고 있는 준혁이는 친구들과 기념사진을 찍어 추억을 남기려고 한다. 그러나 준혁이와 친구들이 방문한 사진관은 다음과 같은 특별한 조건들을 요구했다.

N명의 친구들이 일렬로 줄을 서서 사진을 여러 장 찍으며, 모든 친구들이 적어도 한 장의 사진에 최소 한번씩 등장하게 사진을 촬영하고자 한다. 사진을 촬영하는 방법은 다음과 같다.

1. 한 사람의 독사진을 촬영한다. 이 때 드는 비용은 그 사람의 고유한 비용 A_i원이다.

2. 원하는 위치의 인접한 두 사람의 위치를 바꾼다. 이 때 드는 비용은 C원이다.

3. 연속한 구간에 놓여 있는 친구들의 단체 사진을 촬영한다. 이 때 드는 비용은 사진에 찍히는 한 사람당 B원으로, 전체 비용은 B * (구간 길이) 이다. 단, 기술적인 문제로 단체 사진에는 K명 이상의 친구들이 나와야만 촬영할 수 있다.

현재 친구들은 이미 일렬로 서서 사진 촬영만을 기다리고 있다. 준혁이를 도와 모든 친구들이 적어도 한 장의 사진에 최소 한번씩 등장하도록 사진을 찍을 때의 최소 비용을 구하도록 하자.

사진 촬영 timer 2s memory 1024MB

사진 촬영 2s 1024MB