Infinity Card Decks

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

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.


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



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

Sample Input 2

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

Sample Output 2



There are no comments at the moment.