Bob is playing a card game. He has cards in a line, numbered from to . The -th card has two attributes: the energy required to play the card , and the energy gained upon playing it .
Before the game starts, Bob will first select a contiguous segment of cards from to to form his card deck. Initially, Bob has 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 and , representing the number of cards originally and the initial energy Bob has, respectively.
The second line contains integers , the energy required to play the -th card.
The third line contains integers , the energy gained upon playing the -th card.
Output Specification
Output the number of continuous segments Bob can select as the infinity card deck.
Constraints
Subtask | Points | Additional constraints |
---|---|---|
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 th and th cards.
Sample Input 2
5 10
8 1 6 4 10
7 6 1 8 5
Sample Output 2
5
Comments