Boxen in Boxen

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

A holiday tradition in Woburn C.I. is to give each other boxen (boxes). However, these are no ordinary boxen, they contains 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



  • 0
    grikukan  commented on Jan. 1, 2017, 10:42 a.m.

    According to the statement, answer for each query can be about 1e5 ^ 1e5 (5e5 digits). But we need to output about 1e5 so big numbers, which is obviously impossible.

    • 0
      FatalEagle  commented on Jan. 1, 2017, 10:45 a.m.

      You should output the result modulo 10^9 + 7. I will update the statement shortly, sorry for the inconvenience.