No.3289 Make More Happy Connection
Problem Statement
Yuki-kun feels happy by the amount of a number whenever the same number appears next to each other in a sequence.
Yuki-kun has an empty array $A$, and he performs the following operation $N$ times.
In the $i$-th operation ( $1 \le i \le N$ ), he does one of the following:
- Append $2$ elements to the end of $A$ in the order $x_i$, $y_i$.
- Append $2$ elements to the end of $A$ in the order $y_i$, $x_i$.
For the final array $A$ of length $2N$, define the score $S$ as "the sum over adjacent positions, where a position contributes the value of the element if the adjacent elements are equal and $0$ otherwise", that is, as follows.
$$S=\sum_{\substack{1 \le i < 2N \\ A_i = A_{i+1}}}A_i$$
Find the maximum possible score $S$.
Constraints
- $1 \le N \le 3 \times 10^5$
- $1 \le x_i,y_i \le 10^9$
- All input values are integers.
Input
The input is given from standard input in the following format.
$N$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_N\ y_N$
Output
Output the maximum possible score. End the output with a newline.
Sample
Sample 1
Input
4 1 2 3 2 3 5 5 9
Output
10
When the operations are performed so that $A=(1,2,2,3,3,5,5,9)$, the score is $10$, and this is the maximum.
Sample 2
Input
2 1 6 1 6
Output
6
Sample 3
Input
10 1 5 3 5 3 7 6 2 2 6 6 9 5 4 2 3 1 3 3 2
Output
19
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
kona0001
drken1215