题目描述

圣诞节很快到啦，动物王国里的动物们在排练一个节目。有N只动物从左往右排成一行。第i只动物的身高是h[i]，体重是w[i]。每只动物都要听训练师的指令。

1. 所有动物，向左看！
2. 每只动物都要找出左边那只跟自己身高相同的动物，且离自己最近。假如第j只动物找到第i只离自己最近且身高相同的动物（它们之间隔了j-i-1动物），则第j只动物得到的奖励为这j-i-1只动物的体重之和。如果左边没有与自己身高相等的，则该动物的奖励为0。

训练结束后，训练师想知道，得到最多奖励的动物拿到了多少奖励？

输入格式

第一行，一个整数N。

接下来N行，每行两个正整数：h[i],w[i]。

输出格式

输出一个整数表示最大奖励

样例输入/输出

5 
10 20 
20 10 
20 30 
10 10 
20 20

40

数据规模与提示

$1 \leq N \leq 10^6;1 \leq h[i],w[i] \leq 1000$

时间限制：1000ms.

内存限制：256MB.