공원 산책

지난 한 주 내내 비가 왔다. 미스터 빈은 며칠 동안 집에 틀어박혀 있다가, 햇살이 좋은 오늘 중앙 공원으로 산책을 나갔다. 길을 걷던 그는 "2015년: 빛의 해!"라고 적힌 밝은 간판을 보았다. 그 문구에 기분이 좋아진 미스터 빈은 좋은 일을 하겠다는 마음으로 목적지를 향해 걸음을 옮겼다.

공원에 도착한 그는 크기가 서로 다른 꽃병들을 모아 만든 조형물을 보았다. $i$번째 꽃병의 크기는 $a_i$이고, 일주일 동안 그 안에 $a_i$만큼의 물이 고였다. 미스터 빈은 꽃병에 물이 고여 있으면 안 된다고 생각하고, 정직한 사람답게 상황을 바로잡기로 했다. 그는 모든 꽃병에 구멍을 하나씩 뚫었다. $i$번째 꽃병의 구멍은 직경이 $b_i$이며, 초당 $b_i$만큼의 물이 흘러나온다. 구멍은 모두 같은 순간에 뚫렸다. 미스터 빈은 구멍을 뚫은 뒤 각 시각에 모든 꽃병에 남아 있는 물의 합이 얼마인지 알고 싶어 한다. 그의 질문에 모두 답을 구하라.

첫 줄에 두 정수 $n$, $t$ ($1 \le n \le 10^5$, $1 \le t \le 10^6$)가 주어진다. $n$은 꽃병의 개수이고, $t$는 미스터 빈이 꽃병의 물에 관심을 갖는 시간이다.

다음 $n$개의 줄에는 각각 두 정수 $a_i$, $b_i$ ($0 \le a_i \le 10^9$, $0 \le b_i \le 10^9$)가 주어지며, 이는 $i$번째 꽃병을 나타낸다.

$t+1$개의 정수를 출력한다. 첫 줄에는 초기 시각의 물의 합을, 이후 각 줄에는 다음 시각의 물의 합을 출력한다.