Array Sum

Interview

Time limit5sMemory limit512 MB

Summary

Reorder two arrays to make some sum value repeat as often as possible; report the maximum repeat count and the largest such sum.

Level: Medium6 of 10
Topics: Sorting, Hash map, Greedy
Solved: No attempts yet

Problem

You are given an array $A$ and an array $B$ , each of size $N$ .

You can shuffle the elements of $A$ and the elements of $B$ into any order you like. After shuffling, build the array $C$ by $C[i] = A[i] + B[i]$ .

Let $Y$ be the number that appears most often in $C$ , and let $X$ be how many times it appears. Build $C$ so that $X$ is as large as possible. If several ways of building $C$ reach the same largest $X$ , pick the one whose $Y$ is largest.

Input

The first line contains the array size $N$ ( $3 \le N \le 100000$ ).

The second line contains the $N$ elements of $A$ , and the third line contains the $N$ elements of $B$ , separated by spaces.

Every element of both arrays is an integer that is at least $0$ and less than $100000$ .

Output

Print $X$ and $Y$ on one line, separated by a space.

Examples3

Example 1
Input
```
3
1 1 1
1 1 1
```
Expected output
```
3 2
```
Example 2
Input
```
3
1 1 3
1 1 3
```
Expected output
```
2 4
```
Example 3
Input
```
3
1 2 1
0 1 1
```
Expected output
```
3 2
```