J16 例题-2 排队买票

题目描述

售票窗口会在八点开始卖票，共有 $N$ 个人来买票，第 $i$ 个人买票都有时间花费 $A_i$，第 $i$ 个人可以和他后面的（也就是 $i+1$ 个人组队买票），如果两个人可以一起买票，时间花费为 $B_i$ ； 问： 求这 $n$ 个人最短的购票时间。

输入格式

第一行：一个整数 $N$ ，表示排队的人数； 第二行： $N$ 个整数，第 $i$ 个数字表示第 $i$ 个人单独的购票时间 $A_i$ ； 第三行： $N-1$ 个整数，第 $i$ 个数字表示第 $i$ 个人与 $i+1$ 个人组队购票的时间 $B_i$ 。

输出格式

一个整数，表示这 $n$ 个人最短的购票时间。

样例输入

5
20 25 30 37 32
40 40 43 52

样例输出

112

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据有 $1 \leq N \leq 2000;1 \leq A_i,B_i \leq 1000$ 。