Report Card

Interview

Time limit1sMemory limit256 MB

Summary

Given N (x, y) points, find positive integers a and b up to 100 that minimize the sum of squared residuals of f(x) = ax + b.

Level: Easy3 of 10
Topics: Brute force, Math, Implementation
Solved: No attempts yet

Problem

Dongha failed another course this semester and landed on academic probation again. To stay off the list next time, he decided to study.

Dongha wondered how much study time turns into how many points, so he surveyed $N$ students. Student $i$ studied for $x_i$ hours and scored $y_i$ points.

From this data he wants to estimate the exam score after $x$ hours of study as $f(x) = ax + b$ . Find $a$ and $b$ for him.

A function $f(x)$ that predicts an exam score from study time should keep the gap between $f(x_i)$ and $y_i$ small on every record $(x_i, y_i)$ .

RSS (residual sum of squares) turns that idea into a formula. The smaller the RSS, the better the model fits the data.

$\text{RSS} = \sum_{i=1}^{N}\left(y_i - f(x_i)\right)^2$

Among the positive integers $a$ and $b$ that are at most 100, find the pair that minimizes RSS. The intermediate values grow large, so watch out for overflow.

Input

The first line contains the number of records $N$ . ( $2 \le N \le 100$ )

Each of lines 2 through $N+1$ contains the study time $x_i$ and the exam score $y_i$ of student $i$ , in that order. ( $1 \le x_i, y_i \le 1000$ , and $x_i$ and $y_i$ are integers)

Output

Print $a$ and $b$ that minimize RSS on one line, separated by a space.

No input has more than one pair $(a, b)$ reaching the minimum RSS.

Examples2

Example 1
Input
```
4
1 2
2 3
3 4
4 5
```
Expected output
```
1 1
```
Example 2
Input
```
5
1 10
2 13
3 16
4 19
5 22
```
Expected output
```
3 7
```