#J0003. 机器人【CSP-J模拟赛T3】

机器人【CSP-J模拟赛T3】

题目描述

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

一共有NN秒,在第ii秒,小明可以决定,让机器人顺时针或者逆时针转90°90°,然后沿着当前方向行走AiA_i的距离,其中,顺指针旋转的代价是LiL_i,逆时针旋转的代价是RiR_i

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

输入格式

第一行输入NN

第二、第三、第四行分别输入Ai,Li,RiA_i,L_i,R_i

输出格式

输出一个数字表示答案。

样例输入 #1

2
1 1
10 1
1 10

样例输出 #1

2

样例解释 #1

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

样例输入 #2

3
1 1 1
10 1 10
1 10 20

样例输出 #2

12

样例解释 #2

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

样例输入 #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%的数据:N20N\leq 20

对于65%的数据:Ai35A_i\leq 35

对于100%的数据:2N40,1Li,Ri,Ai1072\leq N\leq 40,1\leq L_i,R_i,A_i\leq 10^7