题目描述

数轴上有 $n$ 个人，编号为 $0,1,\ldots,n-1$。第 $i$ 个人位于坐标 $pos_i$，所有人的位置互不相同，并且输入中按坐标严格递增排列。

Bob 是一名推销员，他只交易一种物品。第 $i$ 个人的供需情况用 $delta_i$ 表示：若 $delta_i>0$，则此人可以提供 $delta_i$ 件物品；若 $delta_i<0$，则此人需要 $-delta_i$ 件物品。保证 $\sum delta_i\ge 0$，因此总供给足以满足总需求。

Bob 初始位于坐标 $0$，手中没有物品。他每秒可以在数轴上向左或向右移动 $1$ 个单位。当 Bob 与某个人处于同一位置时，可以瞬间与其交易任意数量的物品。Bob 可以携带任意多物品，也可以经过某个人所在的位置而暂时不交易。

Bob 的目标是满足所有人的需求。完成后他可以停在任意位置。

求完成目标所需的最少时间。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $pos_i,delta_i$。

输出格式

输出一个整数，表示满足所有需求所需的最少时间。

数据范围

• $1\le n\le 2500$；
• $-10^5\le pos_i,delta_i\le 10^5$；
• $pos_i$ 两两不同且严格递增；
• $\sum_{i=0}^{n-1}delta_i\ge 0$。

样例

输入

3
-10 -5
1 6
100 -1

输出

122

说明

一种最优方案是先从 $0$ 走到 $1$ 取得 $6$ 件物品，再走到 $-10$ 满足 $5$ 件需求，最后走到 $100$ 满足剩余的 $1$ 件需求。总路程为 $1+11+110=122$。