题目背景

如果你选择贪心地往上爬，那么也许后面会掉落很多。
相反如果你足够聪明，暂时往下落后面可能能爬的更高。

题目描述

现在你在玩一个游戏，游戏一共持续 $n$ 秒，刚开始是第 $0$ 秒。
现在你可以控制一个小玩家上下移动，但是每一秒需要按照以下规则来移动：

• 如果第 $i$ 秒小玩家所处的高度值为偶数，则可以选择向上移动 $a_i$ 个单位，或者向下移动 $b_i$ 个单位。

• 如果第 $i$ 秒小玩家所处的高度值为奇数，则必须选择向下移动 $b_i$ 个单位。

小玩家在第 $0$ 秒所处高度为 $0$ 的位置，现在问你，第 $n$ 秒后，小玩家可以达到的最高位置为多少？

输入格式

第一行一个正整数 $n$。
接下来 $n$ 行，每行两个正整数 $a_i,b_i$，依次表示第 $1\sim n$ 秒的 $a$ 和 $b$ 的值。

输出格式

一行一个整数，表示第 $n$ 秒后小玩家可以达到的最高位置。

输入输出样例 #1

输入 #1

5
1 3
2 4
3 3
1 7
1 4

输出 #1

-9

输入输出样例 #2

输入 #2

5
3 2
1 7
9 10
10 3
6 4

输出 #2

8

说明/提示

数据范围：$1\le n\le 5\times 10^5,1\le a_i,b_i\le 10^9$。