계단 함수 근사

실수 함수 $f$를 다른 함수로 근사한다는 것은, 어떤 성질을 만족하면서 $f$ 대신 사용해도 오차가 비교적 작은 실수 함수 $g$를 찾는 것을 뜻한다. 보통 $g$는 $f$보다 단순하고 값을 빠르게 계산할 수 있어야 한다.

계단 함수란 정의역을 $[a, b)$ 꼴의 구간들로 나눌 수 있고 각 구간 위에서 함수 값이 일정한 실수 함수를 말한다. 값이 일정하게 유지되는 이런 극대 구간 하나를 함수의 계단(stair) 이라고 부른다.

여기서 다루는 함수들은 정수 $x$ 좌표에서만 값이 바뀔 수 있다고 가정한다. 즉 정수 $i$에 대해 구간 $(i, i+1)$ 위에서는 항상 일정하며, 우리가 관심을 두는 정의역은 $[0, n)$이다.

계단이 최대 $n$개인 계단 함수 $f$를, 계단이 최대 $k$개인 계단 함수 $g$로 근사하려고 한다. 주어진 매개변수 $p$에 대해 최소화하려는 오차는 다음과 같다.

$\sum_{i=0}^{n-1} \left| f(i) - g(i) \right|^{p}$

$f$의 값들, $g$가 가질 수 있는 계단의 최대 개수 $k$, 그리고 $p$가 주어질 때, 계단이 최대 $k$개인 임의의 계단 함수 $g$로 $f$를 근사할 때의 최소 오차를 구하고 그 값을 기약분수로 출력하여라.

첫째 줄에 세 정수 $n$, $k$, $p$가 공백 하나로 구분되어 주어진다 ($1 \le n \le 4000$, $1 \le k \le 100$, $p \in \{1, 2\}$). $n$은 $f$의 계단 개수이고, $k$는 $g$에 허용되는 계단의 최대 개수이다.

이어지는 $n$개의 줄 중 $i$번째 줄에는 정수 $y_i$가 하나씩 주어진다 ($0 \le y_i \le 1000$). 이는 구간 $[i-1, i)$에서의 $f$의 값이며 $1 \le i \le n$이다.

최소 오차는 분수가 될 수 있다 ($p = 2$일 때 한 계단에서의 최적 상수는 그 구간 값들의 평균이다). 따라서 최소 오차를 기약분수로 출력한다.

최소 오차를 기약분수 $\frac{a}{b}$ (단 $b \ge 1$, $\gcd(a, b) = 1$)로 나타내자. $b = 1$이면 정수 $a$ 하나만 출력한다. 그렇지 않으면 a/b 형태로 (분자, 슬래시, 분모를 공백 없이) 출력한다.