B13 - Supermarket 2 Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

KYOPRO 商店には N 個の品物が売られており、i 番目の品物は A_i 円です。連続する番号の品物を買う方法は全部で N(N+1)/2 通りありますが、この中で合計価格が K 円以内となるような買い方は何通りでしょうか。

制約

  • 1 \leq N \leq 100\,000
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N K
A_1 A_2 \cdots A_N

出力

合計価格が K 円以内となるような買い方が何通りかを求め、一行に出力してください。

入力例 1

7 50
11 12 16 22 27 28 31

出力例 1

13