Robot Competition

Interview

Time limit1sMemory limit1024 MB

Summary

Given the tallest stack height in every row and column of an N by N grid, find the minimum and maximum total number of cubes.

Level: Medium5 of 10
Topics: Greedy, Implementation, Math, Matrix
Solved: No attempts yet

Problem

You have built a robot for a robot competition. One of the tasks the robot must solve is to count the number of cubes in a square grid. The grid has $N$ rows and $N$ columns, and each cell holds a stack of $1$ to $5$ identical cubes. Unfortunately, your robot is not very good at gathering information. All it can do is find the height of the tallest stack in each row and each column. You planned to compensate for this by making the robot very smart. Write a program that, given the information the robot collected, computes the minimum and maximum possible number of cubes in the grid.

Input

The first line contains the integer $N$ , the number of rows and columns in the grid. The second line contains $N$ integers $r\_i$ $(1 \leq r\_i \leq 5)$ , the height of the tallest stack in row $i$ . The third line contains $N$ integers $c\_i$ $(1 \leq c\_i \leq 5)$ , the height of the tallest stack in column $i$ . The input is guaranteed to contain no contradictions, that is, there is always at least one valid placement of cubes that produces the given values.

Output

Print two integers: the minimum and maximum possible total number of cubes in the grid.

Constraints

$3 \le N \le 10$

Hint

These three are the only possible configurations for the first sample. The first two each have a total of 14 cubes, and the third has a total of 15 cubes. So the answer is that the minimum possible total number of cubes is 14, and the maximum possible is 15.

Examples2

Example 1
Input
```
3
2 3 1
3 1 3
```
Expected output
```
14 15
```
Example 2
Input
```
4
5 5 5 5
5 5 5 5
```
Expected output
```
32 80
```