선형 회귀는 너무 쉬워 3

이 문제는 선형 회귀는 너무 쉬워 4와 문제에서 사용하는 식의 차수만 다릅니다.

유림이는 선형 회귀에 자신이 있다. 그래서 MatKor 동아리에서 선형 회귀에 관한 수업을 할 때 집중하지 않았다. 당시 강사였던 동우는 이를 못마땅하게 여겨 유림이에게 과제로 선형 회귀는 너무 쉬워 1과 선형 회귀는 너무 쉬워 2를 내주었고, 유림이는 두 문제를 쉽게 풀었다.

기존의 일반적인 선형 회귀 문제는 다음과 같다. 데이터 $(x\_1,y\_1) ,(x\_2,y\_2) ,\cdots ,(x\_n,y\_n)$이 주어졌을 때, 이를 가장 잘 설명하는 일차함수 $y=ax+b$를 찾는 문제이다. 여기서 주어진 점들 $(x\_i,y\_i)$에 대해 $x\_i$를 통해 얻는 추정치 $\hat{y\_i} =ax\_i+b$로 정의하고, 실제 $y\_i$에서 예측치인 $\hat{y\_i}$를 뺀 값 $y\_i-\hat{y\_i}$를 잔차 $\epsilon\_i$로 정의한다.

선형 회귀 문제는 이 잔차 제곱의 합이 $0$에 가장 가깝게, 즉 $f\_2(a,b) =\displaystyle\sum\_{i=1}^n\epsilon\_i^2=\displaystyle\sum\_{i=1}^n(y\_i-ax\_i-b)^2$이 최소가 되도록 하는 실수 $a$와 $b$를 찾는 문제이다.

동우는 여기에서 더 발전시켜 잔차 $k$제곱의 합 즉, $f\_k(a,b) =\displaystyle\sum\_{i=1}^n\epsilon\_i^k=\displaystyle\sum\_{i=1}^n(y\_i-ax\_i-b)^k$이 $0$에 가장 가깝게 하는 실수 $a$와 $b$을 구하는 문제를 냈다.

이 문제를 풀던 유림이는 너무 어려워서 동우에게 조금만 쉽게 바꿔 달라고 하자 동우는 조금 고민하다 다음과 같은 조건을 추가한다. ”$k=3$일 때만 구해. 그리고 $y$절편이 정해져 있을 때 기울기만 정해. 또, 모든 점의 $x$좌표는 양의 정수, $y$좌표도 정수라고 가정하자.”

이제 유림이가 풀 문제는 다음과 같다. 주어진 $b$에 대해 $f\_3(a) =\displaystyle\sum\_{i=1}^n\epsilon\_i^3=\displaystyle\sum\_{i=1}^n(y\_i-ax\_i-b)^3$이 $0$에 가장 가깝게 하는 실수 $a$를 $a\_3$이라고 할 때, $a\_3$을 구하면 된다.

첫 번째 줄에 데이터의 개수를 의미하는 정수 $n$과 $y$ 절편을 의미하는 정수 $b$가 공백으로 구분되어 주어진다. $(1\le n\le 10^5;$ $-10^6\le b\le 10^6)$

두 번째 줄부터 $n$개의 줄에 걸쳐 한 줄에 하나씩 점의 좌표를 나타내는 정수 $x\_i$와 $y\_i$의 값이 공백으로 구분되어 주어진다. $(1\le x\_i\le 10^6;$ $-10^6\le y\_i\le 10^6)$

이때, 서로 같은 점이 여러 번 주어질 수 있음에 유의하라.

첫 번째 줄에 $f\_3(a)$의 값이 $0$에 가장 가깝게 하는 $a$, 즉, $a\_3$을 출력한다.

답이 여러 가지라면 그중 아무거나 하나 출력한다.

가능한 정답 중 최소 하나 이상과의 절대오차 또는 상대오차가 $10^{-7}$ 이하이면 정답으로 인정된다.