Shinobu likes doughnuts very much.There is a store that sells doughnuts every day. On the i th day the store will sell ai Chocolate Doughnuts and bi cream doughnuts.
You and Shinobu go shopping every day (The order of arrival is represented by an integer Pi, Pi = 0 for Shinobu to arrive at the store first, Pi = 1 for you to arrive at the store first).
If Shinobu goes to the store first, she will choose one kind of doughnut and buy all the doughnuts of this kind,and then you can only choose whether to buy all the remaining doughnuts (you can only choose to buy all or not), and if you go to the store first, you can choose one kind of doughnut and buy all the doughnuts of this kind (of course, you can also buy nothing). Shinobu will buy all the remaining doughnuts when she arrive at the store later than you.
When n days pass, Shinobu will check whether her doughnuts are less than yours, and if they are less than yours, she will eat you angrily.
You want to know the max number of doughnuts you can have without being eaten by Shinobu

The first line of the input contains one integer n ——the number of days

then the following n lines each contains two integer number ai and bi  ——the number of Doughnuts the store sold on the i th day.

The first integer PI in the next n rows represents the order of arrival
If Pi = 0, it represents Shinobu arrive first, followed by an integer Ti representing Shinobu's choice, Ti = 0 indicating Shinobu has bought all ai chocolate doughnuts, Ti = 1 representing Shinobu has bought all bi cream doughnuts.
If PI equals 1, which means you go to the store first, you can choose to buy ai Chocolate Doughnuts or bi cream doughnuts or noting, and then  Shinobu will buy all the remaining doughnuts

0<= ai,bi,n<=100 ,0<=Pi,Ti<=1

Output an integer indicating the max number of doughnuts you can have without being eaten by Shinobu

3
1 2
3 2
4 1
0 1
1
1

6

5
53 73
27 81
48 41
87 83
67 89
0 1
1
1
0 0
1

306