JOI同学的午饭,是在中华料理店买的小笼包。这是一种用小麦粉制成的皮包着馅和热汤的料理,吃的时候,热汤会飞溅出来。
JOI 同学点的小笼包套餐,由馅料不同的 N 个小笼包组成。N 个小笼包等间隔排成一列,编号为 1 到 N。第 i 个小笼包与第 j 个小笼包之间的距离是绝对值 \vert i - j \vert。 JOI 同学按照顺序吃小笼包。最初,所有的小笼包的美味度都是 0。吃第 i 个小笼包时,汤汁向周围飞散,与第 i 个小笼包距离 D_i 以下的小笼包都淋上了汤汁,而被淋上汤汁的小笼包的美味度会增加 A_i。也就是说,吃第 i 个小笼包的时候,第 j 个小笼包 (1 \leq j \leq N 并且 i - D_i \leq j \leq i + D_i) 还没有吃到的话,第 j 个小笼包的美味度就增加 A_i。
JOI 同学要在吃小笼包的顺序上下功夫,让吃的小笼包的美味度的合计最大化。