Infinite Gyro Decks

You are given a sequence of n cards. Each card is represented by a tuple \( (a_i, b_i) \) which means that playing this card costs \( a_i \) fee and rewards you with \( b_i \) fee.

You may choose an interval \( [l, r] \) from the sequence. The cards in this interval form your deck. Initially, you have \( E \) fee, and the deck is randomly shuffled. Then, you play the cards one by one in the order of the deck. After finishing a round (i.e. playing all cards in the deck), the deck is reshuffled randomly and you play again in the new order. This process repeats until you are unable to play the next card (i.e. your current fee is strictly less than the cost \( a_i \) required by that card).

A deck is said to be "gyro infinite" if no matter how the deck is shuffled, you can play infinitely, i.e. the process will never stop. Determine the number of intervals \( [l, r] \) that produce a gyro infinite deck.

Observation: In order for a deck to be gyro infinite, two conditions must be met:

1. The initial fee is sufficient to play every card in the deck. Since any card might appear as the first card in a cycle, we must have \( E \geq \max_{l \le i \le r} a_i \).
2. The net fee change in one complete cycle is nonnegative. In other words, \( \sum_{i=l}^{r} (b_i - a_i) \geq 0 \).

Your task is to count the number of intervals \( [l, r] \) (with \( 1 \le l \le r \le n \)) such that both conditions hold.

Mathematical formulation:

Let \( A = \{a_1, a_2, \ldots, a_n\} \) and \( B = \{b_1, b_2, \ldots, b_n\} \). For an interval \( [l, r] \), define:

[ S(l, r) = \sum_{i=l}^{r} (b_i - a_i), \qquad M(l, r) = \max_{l \le i \le r} a_i. ]

The interval \( [l, r] \) defines a gyro infinite deck if and only if:

[ M(l, r) \le E \quad\text{and}\quad S(l, r) \ge 0. ]

inputFormat

The first line contains two integers \( n \) and \( E \) (the number of cards and the initial fee).

The next \( n \) lines each contain two integers \( a_i \) and \( b_i \) representing the cost and reward of the \( i\)-th card.

\( 1 \le n \le 10^5 \) (if constraints are high, optimized solutions are expected) and \( 1 \le a_i, b_i, E \le 10^9 \).

outputFormat

Output a single integer representing the number of intervals \( [l, r] \) for which the deck is gyro infinite.

sample

3 5
3 4
5 6
4 4

6