All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Shooting Range
Tag(s):

Data Structures, Medium-Hard

Problem
Editorial
Analytics

Three friends Snow Gnome, Small Boy and Xephy were having fun in the biggest park in Lalalandia, when suddenly they saw the shooting range with prizes! As always, Small Boy asked for the biggest prize, and Snow Gnome said he would get it.

The shooting range consists of $$N$$ towers each denoted by $$K_i$$ lines ($$1 \le i \le N$$). Towers are described by blocks from the bottom to the top. Each block consists of $$A_{ij}$$ cubes and the shooter gets $$B_{ij}$$ coins for taking one cube in this block for $$1 \le j \le K_i$$ (see the picture for more explanation).

The shooter gets $$Q$$ shots. He shoots the bullets in straight line on height $$C_l$$. After the bullet shoots the cube, it gets destroyed, and all cubes above it move down. Note that bullet, even after penetrating one tower, continues to go through and never goes down.

Xephy now wants to know how many points for each shot Snow Gnome got. Can you help him with that?

Input format

First line contains single integer $$N$$ - the number of towers.

Next $$N$$ lines describe the tower $$i$$ ($$1 \le i \le N$$) - each contains single integer $$K_i$$. Next $$K_i$$ lines contain the numbers $$A_{ij}$$ and $$B_{ij}$$ for $$1 \le j \le K_i$$ - the number of cubes and the coins for shooting one cube from this block, respectively.

Next line contains $$Q$$ - the number of Snow Gnome's shots. The $$Q$$ lines describe the $$l$$th shot ($$1 \le l \le Q$$) - each containing one integer $$C_l$$ - the height of the $$l$$th shot.

Output format

The output should contain $$Q$$ lines. $$l$$th line should contain single integer - points for Snow Gnome's $$l$$th shot ($$1 \le l \le Q$$).

Constraints:

$$1 \le N \le 10^5$$

$$1 \le K_i \le 10$$

$$1 \le A_{ij} \le 10^8$$

$$1 \le B_{ij} \le 10^9$$

$$1 \le Q \le 10^5$$

$$1 \le C _l \le 10^9$$

SAMPLE INPUT
2
3
1 2
2 3
3 4
1
3 5
3
2
4
6
SAMPLE OUTPUT
8
4
0
Explanation

The picture for the first test:

explanation for 1st test

For the first shot Snow Gnome got $$8$$ points:

shot #1

For the second shot - $$4$$:

shot #2

And the last one he missed:

shot #3

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications