1505: cyw 的学习计划

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：1 AC：1 Score：100.00

Description

cyw 最近收到了一笔奖学金，于是她准备报一些课程来提升自己

但是 cyw 想报的三门课开课时间是完全相同的 n 天，

那么也就是说 cyw 每天只能选择其中一门课去上

而对于第 i 天的课程，第一门课的价格为 a_i，第二门课的价格为 b_i，第三门课的价格为 c_i

同时 cyw 不希望连续两天上同样的课程，这会让她觉得无聊

现在她想知道，在保证每天都上一门课的情况下，学完这 n 天最少需要花多少钱？

Input

第一行只有一个整数 n，表示课程有 n 天。

第二行有 n 个正整数 a_i，表示第一门课每天的价格

第三行有 n 个正整数 b_i，表示第二门课每天的价格

第四行有 n 个正整数 c_i，表示第三门课每天的价格

对于 30% 的数据，1 <= n <= 10

对于 60% 的数据，1 <= n <= 500

对于 100% 的数据中，1 <= n <= 100000，1 <= a_i, b_i, c_i <= 100

Output

输出仅有一行，该行只有一个整数，表示最小花费。

Samples

input:

5 1 3 1 2 2 1 2 3 4 3 4 2 1 5 3

output:

Source

暑假集训