Problem Description

There are $n$ cards forming a sequence. Each card is represented by an ordered pair $(a_i, b_i)$, meaning that playing this card costs $a_i$ energy, and after playing it you gain $b_i$ energy.

Next, you may choose an interval $[l, r]$ and take all cards in this interval as your deck.

At the beginning, your deck will be shuffled into a random order, and you have $E$ energy. Then you will play the cards in this order one by one from front to back.

After you finish playing all cards in this order, your deck will be shuffled randomly again, and you will play them one by one again. You continue doing this until you can no longer play the next card (your current energy is less than the energy cost of the next card), and then you stop.

If a deck can be played infinitely no matter what happens, we say this deck can achieve "infinite spinning top".

Now, determine how many intervals form a deck that can achieve "infinite spinning top".

Input Format

The first line contains two non-negative integers $n, E$, representing the length of the card sequence and the initial energy value $E(1 \leq n \leq 10^6, 0 \leq E \leq 10^9)$.

The next line contains $n$ non-negative integers $a_i(0 \leq a_i \leq 10^9)$, indicating the energy cost to play each card.

The next line contains $n$ non-negative integers $b_i(0 \leq b_i \leq 10^9)$, indicating the energy gained after playing each card.

Output Format

Output one line with one integer, indicating how many intervals form a deck that can achieve "infinite spinning top".

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

4

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

5

Hint

This problem uses bundled subtasks.

For $100\%$ of the testdata, $1 \leq n \leq 10^6$, $0 \leq E, a_i, b_i \leq 10^9$.

• Subtask 1 (20%): $1 \leq n \leq 5000$.
• Subtask 2 (10%): $b_i \geq a_i$.
• Subtask 3 (10%): $E = 0$.
• Subtask 4 (10%): $0 \leq a_i, b_i \leq 1$.
• Subtask 5 (20%): $a_i \times b_i = 0$.
• Subtask 6 (30%): No special constraints.

Translated by ChatGPT 5