Steve cần kiểm tra hệ thống ~n~ trạm đo lượng mưa. Ở trạm thứ ~i~ có một bình chứa:

• Lượng nước ban đầu là ~a_i~.
• Khi mở van xả, mỗi giây bình xả được ~b_i~ đơn vị thể tích (nếu còn đủ nước). Nói cách khác, sau ~s~ giây lượng nước còn lại ở bình ~i~ là: ~\max(0,\ a_i - b_i \cdot s)~.

Tại thời điểm ~0~ (vừa mở van, nước chưa chảy ra), và sau ~1,2,\dots,t~ giây, Steve muốn biết tổng lượng nước còn lại trong tất cả các bình.

Yêu cầu

Với mỗi ~s = 0,1,2,\dots,t~, hãy tính: ~S(s) = \sum_{i=1}^{n} \max(0,\ a_i - b_i \cdot s)~ và in ra lần lượt theo thời gian.

Dữ liệu

• Dòng đầu chứa 2 số nguyên ~n~ và ~t~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa 2 số nguyên ~a_i~ và ~b_i~.

Kết quả

In ra ~t+1~ dòng, dòng thứ ~s+1~ là giá trị ~S(s)~ tương ứng với thời điểm ~s~ giây (~s~ chạy từ ~0~ đến ~t~).

Ví dụ

Ví dụ 1

Input

6 6
12 2
10 3
3 1
5 4
7 2
9 1

Output

46
33
23
14
9
6
3

Giải thích

Ví dụ 1

Tổng lượng nước ban đầu (thời điểm ~0~) là ~12+10+3+5+7+9 = 46~.

Sau ~1~ giây, mỗi bình giảm lần lượt ~2,3,1,4,2,1~ (không bình nào về 0), tổng còn lại là ~33~.

Tương tự tính cho các thời điểm tiếp theo thu được dãy kết quả như mẫu.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10^5~
• ~1 \le t \le 10^6~
• ~0 \le a_i \le 10^9~
• ~0 \le b_i \le 10^9~