Math Notebook

Interview

Time limit1sMemory limit128 MB

Summary

Choose a contiguous block from both sequences to maximize its dot product with the reversed second block.

Level: Medium5 of 10
Topics: Brute force, Array
Solved: No attempts yet

Problem

You are given two integer sequences, each of length $N$ . Their blurriness is computed as follows: reverse the second sequence, multiply the two numbers that now share the same position, and add up all of those products.

3	-4	-3	-2	2	0
-3	0	5	-1	3	2

For example, the blurriness of the two sequences above is $3 \times 2 + (-4) \times 3 + (-3) \times (-1) + (-2) \times 5 + 2 \times 0 + 0 \times (-3) = -13$ .

You may delete $B$ columns from the front and $E$ columns from the back to make the blurriness as large as possible. $B$ and $E$ may be $0$ , and deleting a column removes the same position from both sequences at once. At least one column must remain, so $B + E < N$ .

Find $B$ and $E$ that maximize the blurriness, together with that maximum blurriness.

Input

The first line contains the length of the sequences $N$ $(1 \le N \le 2000)$ .

Each of the next two lines contains one sequence of space-separated integers. Every number is between $-1000$ and $1000$ inclusive.

Output

On the first line, print $B$ and $E$ that maximize the blurriness, separated by a space $(0 \le B,\ 0 \le E,\ B + E < N)$ .

If several pairs $(B, E)$ reach the maximum, print the one with the smallest $B$ ; if there is still a tie, print the one with the smallest $E$ .

On the second line, print the maximum blurriness.

Examples3

Example 1
Input
```
6
3 -4 -3 -2 2 0
-3 0 5 -1 3 2
```
Expected output
```
0 3
24
```
Example 2
Input
```
5
1 1 1 1 1
2 2 2 2 2
```
Expected output
```
0 0
10
```
Example 3
Input
```
5
5 -5 -5 -5 5
-5 -5 5 -5 -5
```
Expected output
```
0 2
75
```