Enjoy Arithmetic Progressions

Young Andrew loves arithmetic progressions. His even younger sister Anya wrote a sequence of numbers on the blackboard. Now Andrew wants to split this sequence into several arithmetic progressions. For example, the sequence \textbf{1}\ \textbf{2}\ \textbf{5}\ \textbf{7}\ \textbf{9}\ \textbf{11}\ \textbf{3} can be split into three arithmetic progressions: $\text{1}\text{2}$, \textbf{5}\ \textbf{7}\ \textbf{9}\ \textbf{11}, and $\text{3}$. There is another way to split it into three progressions ($\text{1}\text{2}$, $\text{5}\text{7}\text{9}$, and $\text{11}\text{3}$), but it is impossible to split it into two or fewer progressions.

Obviously, Andrew would like to split the sequence into as few progressions as possible. He is even willing to change some of the numbers to make the resulting number of progressions smaller. But it would be boring to just change all the numbers to \textbf{1}\ \textbf{2}\ \textbf{3}\ldots.

So Andrew decided to assign a score of $\text{c}$ to each change operation, and a score of $\text{p}$ to each resulting arithmetic progression. If he changes n_c numbers and splits the result into n_p progressions, his total score is c n_c + p n_p. He wants his total score to be as small as possible.