Description

今天不是活动课，但是小A说数学老师生病了，这节课上活动课，于是小A带着小朋友们做游戏。

今天的游戏是:老鹰捉小鸡。小A扮演老鹰，同学们扮演小鸡。不过不同于传统的游戏，今天的游戏中，小A不动，而是由同学们发起攻击。

n名同学们站成了-排，从队首到队尾依次编号为第1 ~n名同学。小A给了每名同学一个胸针, 胸针.上有两个数字，对于第i名同学，其胸针上的两个数字分别为a;和bi。

同学们可以发起任意次行动，每次行动可以是攻击或调整。

●攻击:队首的同学对小A发起攻击，假设该名同学的编号为p ,则会对小A造成ap的伤害。同时小A会发动神技“反弹”，对同学们造成bp的伤害，这会让从队首开始的共bp个同学脱离队伍，无法参加游戏。注意:如果队伍中不足bp名同学，则队首的这位同学无法发动攻击。

●调整:队首的同学进行调整，转移到队尾。注意:同学们的编号是不会更改的，如:开始队伍为1,2,3,4,5; 调整一 次后为2,3,4,5,1。

小A说:“有一-种攻击方案可以对我造成最多的伤害总和，如果你们能够找到，我会给你们额外100张免作业卡哦~”。

同学们太想要免作业卡了，聪明的你能帮帮他们吗?

Input

第一行一个数字n,表示同学的个数

第二行共n个数字,分别为b1, b....第三行共n个数字,分别为a1, a...n.n≤40

1≤a;,b;≤10000