配点:400400

問題文

分岐のない 11 本の道のうえに,11 から KK までの番号のついた,KK 個のと呼ばれる地点が順に並んでいます.
ii と場 i+1i+1 とは di  [m]d_i \; \scriptsize \mathrm{[m]} 離れています. (1i<K)\scriptsize (1 \leq i < K)

MojaMoja 君は現在,既に 10100  []10^{100} \; \scriptsize \mathrm{[円]} を所持していますが,更に資産を増やしたいと思っています.
そこで,次のようなゲームに参加することにしました:

  • 1l<rK1 \leq l < r \leq K を満たす 22 整数 l,rl, r を選び,馬に乗って場 ll から 場 rr へ移動する.
  • 馬の走る速さは,はじめ 0  [m/]0 \; \scriptsize \mathrm{[m/秒]} であり,1  []1 \; \scriptsize \mathrm{[円]} を支払うごとに 1  [m/]1 \; \scriptsize \mathrm{[m/秒]} ずつ速く走れるように改造できる.すなわち,p  []p \; \scriptsize \mathrm{[円]} を払うことで p  [m/]p \; \scriptsize \mathrm{[m/秒]} で走ることができるようになる.( pp は非負整数)
  • T  []T \; \scriptsize \mathrm{[秒]} 以内に場 ll から場 rr へ移動することができれば,ゲームをクリアしたとみなされる.
  • ゲームをクリアしたとき,場 ii と場 i+1i+1 との間を通過したごとに,報酬として vi  []v_i \; \scriptsize \mathrm{[円]} を得る.(1i<K)\scriptsize (1 \leq i < K)
  • T  []T \; \scriptsize \mathrm{[秒]} 以内に到達できなかった場合の報酬はない.

適切に馬を改造することによって「『報酬として得る金額』から『そのための馬の改造に費やした金額』を引いた差額」(利益) を正とすることができるような l,r  (l<r)l,r \; \scriptsize (l < r) の選び方は何通りあるでしょうか?
求めてください.

制約

  • 1Φ1051 \leq \Phi \leq 10^5
  • 1<K1 < K
  • ϕΦϕ(K)106\sum_{\phi} \Phi_{\phi}(K) \leq 10^6
  • 0<T<2300 < T < 2^{30}
  • 0<di  (1i<K)0 < d_i \; \scriptsize (1 \leq i < K)
  • 0vi  (1i<K)0 \leq v_i \; \scriptsize (1 \leq i < K)
  • 1i<Kdi,1i<Kvi<230\displaystyle \sum_{1 \leq i < K} d_i, \displaystyle \sum_{1 \leq i < K} v_i < 2^{30}
  • 入力はすべて整数

入力

各テストケースの入力は,それぞれ以下の形式で与えられる:

KTK \enspace T
d1d2dK1d_1 \enspace d_2 \enspace \ldots \enspace d_{K-1}
v1v2vK1v_1 \enspace v_2 \enspace \ldots \enspace v_{K-1}

出力

答えを出力せよ.

サンプル

入力例1
1
5 3
7 9 5 4
3 1 2 3
出力例1
2

(l,r){(3,5),(4,5)}(l, r) \in \{\, (3, 5), (4, 5) \, \} のとき,可能です.

たとえば (l,r)=(3,5)(l, r) = (3, 5) を選んだとします.
3  []3 \; \scriptsize \mathrm{[円]} を掛けて馬を改造し,3  [m/]3 \; \scriptsize \mathrm{[m/秒]} で走れるようにすると,場 33 から場 55 までは 5+4=9  [m]5 + 4 = 9 \; \scriptsize \mathrm {[m]} ありますから,3  []3 \; \scriptsize \mathrm{[秒]} 以内(ちょうど)に到達することが可能です.
また,場 33 から 場 55 までを時間内に移動できた場合,報酬として 2+3=5  []2 + 3 = 5 \; \scriptsize \mathrm{[円]} を得ることができるので,これから改造に用いた 3  []3 \; \scriptsize \mathrm{[円]} を引いても,利益として 2  []2 \; \scriptsize \mathrm{[円]} が残ります.
したがって (l,r)=(3,5)(l, r) = (3, 5) は満たします.

たとえば (l,r)=(1,4)(l, r) = (1, 4)(l,r)=(2,5)(l, r) = (2, 5) の場合,どのように馬を改造しても正の利益を得ることはできません. (報酬を得るためには,T  []T \; \scriptsize \mathrm{[秒]} 以内に移動を完了する必要があることに注意してください.)

提出


Go (1.21)