14930번 - 구슬 (BEAD)

물리를 사랑하는 민준이는 집에 마찰이 없는 무한한 수직선과 완전탄성충돌을 하고 질량이 동일하며 크기를 무시할 수 있는 구슬 N(1 ≤ N ≤100,000)개를 구비해놓고 있다. 어느 날 민준이는 모션캡처분석기기를 활용하기 위해 N개의 구슬 중 하나만 빨간색으로 색칠한 뒤 실을 연결해 N중 진자 실험을 하고 있었다. 이를 해석역학적으로 분석하며, r과 θ의 관계를 파악하던 중 구슬의 질량에 의한 장력을 이기지 못한 실들이 한 번에 끊어져 수직선 위에 널부러지게 되었다. 각각 다른 위치 x_i에 떨어져 저마다의 초속도 v_i를 가지고 운동하게 된 구슬을 보며 민준이는 가슴 아파 했지만 곧 새로운 물리 문제를 떠올리는 데에 성공한다! 바로 t(1 ≤ t ≤10⁹)초 후 빨간 구슬의 위치를 구하는 것이다! 하지만 민준이는 지나치게 많은 구슬의 양에 그만 t초 동안 정신을 잃고 말았다. 민준이가 깨기 전에 답을 구해 민준이를 행복하게 해 주자!

첫째 줄에 구슬의 개수 N과 시간 t가 주어진다.

둘째 줄부터 N개의 줄에는 x_i와 v_i가 주어진다. (-10⁹ ≤ x_i, v_i ≤ 10⁹)

단, 빨간 구슬은 입력에서 첫 번째로 주어지는 구슬이며, v가 음수인 경우는 –x방향으로 진행함을 의미한다.

주어지는 모든 수는 정수이다.

t 초 후 빨간 구슬의 위치를 출력한다. 이 값이 정수임은 보장된다.

2/7초 후 빨간 구슬이 2번 구슬과 충돌한 뒤 2초 후 4번 구슬과 충돌하고 5/2초 후 다시 2번 구슬과 충돌해 3초 후에는 12의 위치에 있게 된다.

완전탄성충돌이란 운동량과 운동에너지 모두 보존되는 충돌을 의미한다.