Azerbaijan is a country rich in natural resources, and thanks to its oil production, its citizens can use gasoline at a very low cost. The capital of Azerbaijan, Baku, has $N$ intersections and $N-1$ bidirectional roads. Baku is a city that is long from north to south. The intersections are arranged in a straight line from north to south, numbered from $1$ to $N$ starting from the northernmost intersection. There are both old roads and new roads. The $N-1$ old roads connect intersection $i$ and intersection $i+1$ for each $1 \le i < N$. The $M$ new roads each connect two distinct intersections that are not already connected by an old road. There is at most one road connecting any pair of intersections.

Due to recent financial difficulties, the capital city of Baku has decided to install toll gates on some of the roads to collect tolls. Since collecting tolls on too many roads might cause public dissatisfaction, they will collect tolls on exactly $2$ roads. The toll is $1$ manat (the currency of Azerbaijan) every time a car passes through a toll gate. If a car passes through two toll gates, it must pay the toll both times.

Every intersection has $N-1$ cars. All cars at an intersection will travel to a different intersection than their current location. When traveling from intersection $u$ to intersection $v$, the driver chooses the path with the minimum toll. (Gasoline is cheap in this country.)

Write a program that determines the two roads that can collect the maximum total toll when all cars have moved to their destinations.

You must implement the following function:

• long long findEdges(int N, int A[], int B[]): This function is called exactly once. It provides the layout of the intersections and roads. $N$ is the number of intersections. $A$ and $B$ are arrays (vectors) of size $M$. Intersection $A[i]$ and intersection $B[i]$ are connected by a new road. Note that $i$ is between $0$ and $M-1$. You must return the maximum total toll that can be collected by placing toll gates on two roads given the intersection and road situation.

Implementation Details

You must submit exactly one file named oil.cpp. This file must implement the following function:

• long long findEdges(int N, int A[], int B[])

This function must operate as described above. You may, of course, create other functions to use internally. The submitted code must not perform I/O or access other files.

Subtasks

• Subtask 1 [10 points]: $3 \le N \le 100$, $0 \le M \le 100$
• Subtask 2 [13 points]: $3 \le N \le 2,000$, $0 \le M \le 2,000$
• Subtask 3 [48 points]: $3 \le N \le 100,000$, $0 \le M \le 100,000$
• Subtask 4 [29 points]: $3 \le N \le 500,000$, $0 \le M \le 500,000$

Examples

Input 1

4 3
3 1
2 4
1 4

Output 1

findEdges( 4, {3, 2, 1}, {1, 4, 4} ) -> 0

Input 2

4 1
1 3

Output 2

findEdges( 4, {1}, {3} ) -> 8

Input 3

4 0

Output 3

findEdges( 4, { }, { } ) -> 14