問題一覧 > 通常問題

No.3289 Make More Happy Connection

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 95
作問者 : kona0001 / テスター : tobisatis RyosukeFukatani koba-e964 ir5 drken1215
お気に入りにしたユーザー ProblemId : 12634 / 自分の提出
問題文最終更新日: 2025-09-24 01:33:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 485 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。