Problem Description

There are $n$ cards forming a sequence, each represented by a tuple $(a_i, b_i)$, meaning that playing this card requires $a_i$ units of cost and yields $b_i$ units of cost afterward.

You can choose an interval $[l, r]$ to extract the cards within this interval as your deck.

Initially, your deck will be shuffled in a random order and you have $E$ units of cost. You will then play the cards from the front to the back of this shuffled order.

After playing all the cards in the shuffled order, the deck will be shuffled again, and you will play the cards in the new order, repeating this process until you cannot play the next card (the current cost is less than the cost required by the next card).

If a deck can be played indefinitely under any circumstances, we call this deck "top infinite."

Now, calculate how many interval-based decks can be "top infinite."

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$ respectively $(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)$, representing the cost required to play each card.

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

Output Format

Output a single integer representing the number of interval-based decks that can be "top infinite."

Sample Input and Output

Sample Input #1

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

Sample Output #1

4

Sample Input #2

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

Sample Output #2

5

Notes

This problem uses subtask-based testing.

For $100\%$ of the data, $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 restrictions.

见题面 Input 部分

见题面 Output 部分