#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/5/problems/C

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/5/problems/C

Repovive

Repovive.

Back

Code

Upload

Submissions

Learn

5C. Christmas Gifts

1500 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

It is Christmas, and Santa wants to give gifts to children standing in a line. There are $n$ children, numbered from $1$ to $n$ from left to right.

For each child $i$ , two numbers $a_i$ and $b_i$ are specified. Santa will decide how many gifts $g_i$ to give to each child.

Child $i$ is happy if they receive at least $a_i$ gifts, and also they are not too far behind any adjacent child: compared to each neighbor (if it exists), child $i$ may have at most $b_i$ fewer gifts.

Formally, the conditions are $g_i \ge a_i$ for all $i$ , and additionally $g_i \ge g_{i-1}-b_i$ for $i>1$ and $g_i \ge g_{i+1}-b_i$ for $i<n$ .

Find the minimum possible value of $\sum_{i=1}^n g_i$ such that all children are happy.

Constraints

$1 \le t \le 100$
$1 \le n \le 2 \times 10^5$
$0 \le a_i, b_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Input

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \quad b_1 \\ a_2 \quad b_2 \\ \vdots \\ a_n \quad b_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

Case 4

Explanation

Case 1

$n=3$ , all children have $(a_i, b_i) = (5, 2)$

Each child needs $\ge 5$ gifts and tolerates neighbors having up to $2$ more. Distribution $[5,5,5]$ works. Total: 15.

Case 2

$n=4$ , values $(1,0), (1,0), (10,0), (1,0)$

With $b_i=0$ , no child tolerates any difference, so all must receive equal gifts. Child 3 needs $\ge 10$ , forcing $[10,10,10,10]$ . Total: 40.

Output

Case 1

Case 2

Case 3

Case 4

It is Christmas, and Santa wants to give gifts to children standing in a line. There are $n$ children, numbered from $1$ to $n$ from left to right.

For each child $i$ , two numbers $a_i$ and $b_i$ are specified. Santa will decide how many gifts $g_i$ to give to each child.

Formally, the conditions are $g_i \ge a_i$ for all $i$ , and additionally $g_i \ge g_{i-1}-b_i$ for $i>1$ and $g_i \ge g_{i+1}-b_i$ for $i<n$ .

Find the minimum possible value of $\sum_{i=1}^n g_i$ such that all children are happy.

Constraints

$1 \le t \le 100$
$1 \le n \le 2 \times 10^5$
$0 \le a_i, b_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \quad b_1 \\ a_2 \quad b_2 \\ \vdots \\ a_n \quad b_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

$n=3$ , all children have $(a_i, b_i) = (5, 2)$

Each child needs $\ge 5$ gifts and tolerates neighbors having up to $2$ more. Distribution $[5,5,5]$ works. Total: 15.

$n=4$ , values $(1,0), (1,0), (10,0), (1,0)$

With $b_i=0$ , no child tolerates any difference, so all must receive equal gifts. Child 3 needs $\ge 10$ , forcing $[10,10,10,10]$ . Total: 40.