New Year's '17 P8 - Boxen in Boxen

View as PDF

Submit solution


Points: 25
Time limit: 2.5s
Memory limit: 256M

Author:
Problem type

A holiday tradition in Woburn C.I. is to give each other boxen (boxes). However, these are no ordinary boxen, they contain gifts, such as foxen (foxes) or more boxen. When one receives a fox, they gain a happiness of F, a constant given at the beginning of the input. You have one species of foxen and a number of different species of boxen.

These boxen have strange properties, they contain exactly one fox or box (which may in turn contain more boxen), regardless of size. No box can directly or indirectly contain itself. Each box has a difficulty value d_i, and multiplier value b_i. The happiness given in a box is equal to the following formula:

\displaystyle H_i = b_i*pre_i-d_i

Where pre_i is the happiness of the box (or fox) that it contains.

imaxblue has a list of N boxen. For index i, imaxblue would like to know the maximum happiness that can be created by packing zero or more boxen (and also a single fox), in any order, that are listed before or on that index. Note that if you use zero boxen, the happiness is just F.

Input Specification

2 integers, N (N \le 100\,000) and F (1 \le F \le 100\,000).
N lines, each with 2 integers: b_i and d_i (1 \le b_i, d_i \le 100\,000).

Output Specification

N lines, each with an integer: the answer to each of imaxblue's queries. Since the answer can be large, please output the value modulo 1\,000\,000\,007 (= 10^9 + 7).

Sample Input

2 3
2 8
7 12

Sample Output

3
10

Comments

There are no comments at the moment.