There is a sequence of $n$ cards, where each card is represented by a pair $(a_i, b_i)$, meaning that playing this card requires $a_i$ energy and yields $b_i$ energy after it is played.

You can choose an interval $[l, r]$ and take the cards in this interval to form your deck.

Initially, your deck is arranged in a random order and you have $E$ energy. You then play the cards in this arrangement one by one from front to back. After you finish playing all the cards in the current arrangement, your deck is randomly reordered again, and you continue playing them in the new order. This process stops when you cannot play the next card (i.e., your current energy is less than the energy required to play the next card).

If a deck can be played indefinitely regardless of the order of cards, we call this deck "Gyro-Infinite".

Calculate how many intervals form a "Gyro-Infinite" deck.

Input

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

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

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

Output

Output a single integer representing the number of intervals that form a "Gyro-Infinite" deck.

Examples

Input 1

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

Output 1

4

Input 2

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

Output 2

5

Constraints

This problem uses subtask-based testing.

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

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