問題文

自分の魅力に気づいたカツサンドくんは、カツサンドのお店を開くことにしました。

お店は $N$ 日間営業し、$i$ 日目には $A_i$ 枚のパンと $B_i$ 枚のカツを入荷します。 パンを $2$ 枚、カツを $1$ 枚使うことで $1$ 個のカツサンドを作ることができます。

カツサンドくんが $N$ 日間で作ることのできるカツサンドの個数の最大値を求めてください。 なお、余った材料はその日の夜に廃棄しなければならず、別の日に使うことはできません。

制約

入力は以下の条件を満たす。

• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq A_i,B_i \\leq 10^9$
• 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_N$ $B_N$

出力

カツサンドくんが $N$ 日間で作ることのできるカツサンドの個数の最大値を出力せよ。

入力例 1

3
10 5
100 1
1 100

出力例 1

6

• $1$ 日目はぴったり $5$ 個のカツサンドを作ることができます。
• $2$ 日目はパンを $2$ 枚、カツを $1$ 枚使うことで $1$ 個のカツサンドを作ることができます。たくさんのパンが余ってしまいました。
• $3$ 日目はパンが $1$ 枚しかないため一つもカツサンドを作ることができません。今度はたくさんのカツが余ってしまいました。

合計 $5+1+0 = 6$ 個のカツサンドを作ることができます。

入力例 2

7
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

出力例 2

3500000000