Beads

Minjun runs a bead experiment on a frictionless number line of infinite length. There are $N$ beads. Each bead has negligible size, and all beads have the same mass. When two beads hit each other, the collision is perfectly elastic.

Minjun painted exactly one bead red. At time $0$, bead $i$ is at position $x_i$ and starts moving with initial velocity $v_i$. A bead changes its velocity only when it collides with another bead.

Find the position of the red bead after $t$ seconds.

The first line contains the number of beads $N$ and the time $t$. ($1 \le N \le 100000$, $1 \le t \le 10^9$)

Each of the next $N$ lines contains the position $x_i$ and the initial velocity $v_i$ of bead $i$. ($-10^9 \le x_i, v_i \le 10^9$)

The red bead is the one given first in the input. A negative $v_i$ means the bead moves in the $-x$ direction.

All given numbers are integers, and the bead positions are distinct.

Print the position of the red bead after $t$ seconds. This value is guaranteed to be an integer.

A perfectly elastic collision conserves both momentum and kinetic energy. When two beads of equal mass collide perfectly elastically, they exchange velocities.

In the sample input the red bead hits bead 2 at time $2/7$, bead 4 at time $2$, bead 2 again at time $9/4$, and bead 4 again at time $5/2$. At time $3$ it is at position $12$.