#822. 小码君过马路

小码君过马路

题目描述

小码君要赶上学校上学,但是路上有着非常非常多的红绿灯,已知相邻的两个路口距离为 AiA_i 千米 (1i<N)(1\le i < N),每个路口的红灯时间为 RiR_i,绿灯时间为 GiG_i,没有黄灯,现在有一辆车从距离 11 号十字路口 MM 千米的位置出发,且此时所有路口的红绿灯刚好从红灯跳到绿灯,问这辆车通过每个路口的时间(不能闯红灯,这辆车的速度为 11 千米每分钟)。

输入格式

第一行两个正整数 NNMM

第二行 N1N-1 个正整数 AiA_i

第三行 NN 个正整数 RiR_i,为红灯时间(分钟)

第四行 NN 个正整数 GiG_i,为绿灯时间(分钟)

输出格式

NN 行,每行一个正整数,为这辆车通过每个十字路口的最早时间。

样例 #1

样例输入 #1

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

样例输出 #1

5
7
11
14
16

提示

对于 50%50\% 的数据 N1000N\le 1000

对于 100%100\% 的数据 N105N\le 10^5M,Ai10M,A_i\le 10RiGi5R_i,G_i\le 5