题目描述

小明有一个机器人，一开始在坐标原点，方向是朝着$X$轴正方向的。

一共有$N$秒，在第$i$秒，小明可以决定，让机器人顺时针或者逆时针转$90°$，然后沿着当前方向行走$A_i$的距离，其中，顺指针旋转的代价是$L_i$，逆时针旋转的代价是$R_i$。

小明希望结束行走时，机器人离坐标系原点的欧几里得距离最小，问：小明最少要付出多少代价。

输入格式

第一行输入$N$。

第二、第三、第四行分别输入$A_i,L_i,R_i$。

输出格式

输出一个数字表示答案。

样例输入 #1

2
1 1
10 1
1 10

样例输出 #1

2

样例解释 #1

小明随便怎么选，最终都会停留在$±1,±1$坐标上，距离原点的距离永远是一样的，还不如选便宜的。

样例输入 #2

3
1 1 1
10 1 10
1 10 20

样例输出 #2

12

样例解释 #2

小明第一秒选择逆指针旋转，花费$1$，走到了$(0,1)$，第二秒选择顺时针旋转，花费$1$，走到了$(1,1)$，第三秒选择顺时针旋转，花费$10$，走到了$(1,0)$。一共花费$12$。

样例输入 #3

10
1 2 4 8 16 16 8 4 2 1
10 54 12 45 1 45 12 45 12 45
65 45 78 45 12 5 12 32 12 12

样例输出 #3

197

数据范围

对于20%的数据：$N\leq 20$。

对于65%的数据：$A_i\leq 35$。

对于100%的数据：$2\leq N\leq 40,1\leq L_i,R_i,A_i\leq 10^7$。