有一吸塵器、\(N\) 個房間，編號從 1\(n。 每個房間有不同量的灰塵，吸塵器於房間\)i\(第一秒可以吸\)a_i\(單位的灰塵，隨著時間的遞增，吸的灰塵量也會遞減，遞減關係呈線型，每秒會比前一秒少吸\)b_i\(的灰塵，直到可以吸的灰塵量歸零為止。 吸塵器一開始位於一號房。 從\)i\(房前往\)i+1\(房需\)t_i\(的時間。 今日有\)T~的時間可以吸塵， 球最多可吸的灰塵量。

輸入格式

第一行為\(N\)，表有\(N\)房間 \(N≤1000\) 第二行有\(T\)，表有\(T\)秒的打掃時間 第三行有\(N-1\)個數 \(t_i\) 第四行有\(N\)個數 \(a_i\) 第五行有\(N\)個數 \(b_i\)

輸出格式

輸出最多可以吸到的灰塵量

範例輸入

6
20
3 5 2 4 2
1 4 2 9 100 99
1 1 1 3 11 9

範例輸出

435