Bob is playing a card game. He has ~N~ cards in a line, numbered from ~1~ to ~N~. The ~i~-th card has two attributes: the energy required to play the card ~a_i~, and the energy gained upon playing it ~b_i~.

Before the game starts, Bob will first select a contiguous segment of cards from ~L~ to ~R~ to form his card deck. Initially, Bob has ~M~ energy. Once he has his card deck, Bob shuffles it randomly and begins playing the cards in the order they appear. After playing the last card in the deck, the cards are shuffled again, and Bob continues the cycle. However, there's a catch - Bob must ensure he has enough energy to play each card in the deck. If he lacks the required energy to play a card, the game ends.

Bob defines a card deck as an infinity card deck if he can perpetually cycle through playing cards without facing an energy shortage, regardless of how the cards are shuffled each time. Your task is to help Bob determine the number of such infinity card decks within the original sequence of cards.

Input Specification

The first line contains two integers ~N~ and ~M~ ~(1 \leq N \leq 10^6, 1 \leq M \leq 10^9)~, representing the number of cards originally and the initial energy Bob has, respectively.

The second line contains ~N~ integers ~a_i~ ~(0 \leq a_i \leq 10^9)~, the energy required to play the ~i~-th card.

The third line contains ~N~ integers ~b_i~ ~(0 \leq b_i \leq 10^9)~, the energy gained upon playing the ~i~-th card.

Output Specification

Output the number of continuous segments Bob can select as the infinity card deck.

Constraints

Subtask	Points	Additional constraints
~1~	~20~	~1 \le N \le 5000~
~2~	~10~	~a_i \le b_i~
~3~	~10~	~M = 0~
~4~	~10~	~0 \le a_i, b_i \le 1~
~5~	~20~	~a_i \times b_i = 0~
~6~	~30~	No additional constraints

Sample Input 1

5 10
9 10 10 0 2
8 5 6 2 5

Sample Output 1

4

Explanation

One of the infinity card decks is to select the ~4~th and ~5~th cards.

Sample Input 2

5 10
8 1 6 4 10
7 6 1 8 5

Sample Output 2

5