题目描述

输入格式

第一行一个正整数N。<o:p></o:p>

第二行共包括N个正整数，第<v:shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"> <v:stroke joinstyle="miter"></v:stroke> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0"></v:f> <v:f eqn="sum @0 1 0"></v:f> <v:f eqn="sum 0 0 @1"></v:f> <v:f eqn="prod @2 1 2"></v:f> <v:f eqn="prod @3 21600 pixelWidth"></v:f> <v:f eqn="prod @3 21600 pixelHeight"></v:f> <v:f eqn="sum @0 0 1"></v:f> <v:f eqn="prod @6 1 2"></v:f> <v:f eqn="prod @7 21600 pixelWidth"></v:f> <v:f eqn="sum @8 21600 0"></v:f> <v:f eqn="prod @7 21600 pixelHeight"></v:f> <v:f eqn="sum @10 21600 0"></v:f> </v:formulas> <v:path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></v:path> <o:lock aspectratio="t" v:ext="edit"></o:lock> </v:shapetype><v:shape id="图片_x0020_118" alt="i" type="#_x0000_t75" o:spid="_x0000_i1025" style="visibility: visible; width: 3.75pt; height: 9.75pt"> <v:imagedata o:title="" src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image001.gif"></v:imagedata> </v:shape>个正整数表示Ai。<o:p></o:p>

第三行共包括N个正整数，第<v:shape id="图片_x0020_121" alt="i" type="#_x0000_t75" o:spid="_x0000_i1026" style="visibility: visible; width: 3.75pt; height: 9.75pt"> <v:imagedata o:title="" src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image001.gif"></v:imagedata> </v:shape>个正整数表示Bi。<o:p></o:p>

输出格式

共一行，包括一个正整数，表示在合法的选择条件下，可以获得的能量值总和的最大值。<o:p></o:p>

<o:p></o:p>

4
3 4 5 12
9 8 30 9

39

数据范围与约定

1<=N<=1000,1<=Ai,Bi<=10^6