### Woburn Challenge 2018-19 Round 3 - Senior Division

## Problem 3: Counterpicking

Jessie's been training hard, and is ready to go out there and claim some new Pokémon for Team Rocket fair and square! Or at least, by beating some Pokémon trainers in battles fair and square, and then proceeding to steal their Pokémon.

Jessie has `N` (1 ≤ `N` ≤ 300,000) Pokémon at her disposal, with the `i`-th one having two traits of interest — a Strength of `A _{i}` and a Speed of

`B`(1 ≤

_{i}`A`,

_{i}`B`≤ 10

_{i}^{9}).

She'll be battling against `M` (1 ≤ `M` ≤ 300,000) trainers, one after another, each with a single Pokémon. In each battle, Jessie will choose one of her `N` Pokémon to use in it. There are no restrictions regarding her choices — for example, she may choose to use any of her Pokémon either in multiple battles, or not at all.

Each trainer's Pokémon is vulnerable against the Strength and Speed traits to various degrees, based on the values `X _{i}` and

`Y`(1 ≤

_{i}`X`,

_{i}`Y`≤ 10

_{i}^{9}). Battle Effectiveness is a measure of how effective Jessie's chosen Pokémon is against a trainer's Pokémon. If Jessie chooses to use her

`j`-th Pokémon in the

`i`-th battle, the resulting Battle Effectiveness will be

`X`×

_{i}`A`+

_{j}`Y`×

_{i}`B`.

_{j}For each of the `M` battles, help Jessie determine the maximum possible Battle Effectiveness that she can achieve by choosing an optimal Pokémon to use. Please note that the answer may not fit within a 32-bit signed integer.

### Subtasks

In test cases worth 6/26 of the points, `N` ≤ 2000 and `M` ≤ 2000.

### Input Format

The first line of input consists of a single integer, `N`.

`N` lines follow, the `i`-th of which consists of two space-separated integers, `A _{i}` and

`B`, for

_{i}`i`= 1..

`N`.

The next line consists of a single integer,

`M`.

`M`lines follow, the

`i`-th of which consists of two space-separated integers,

`X`and

_{i}`Y`, for

_{i}`i`= 1..

`M`.

### Output Format

`M` lines, the `i`-th of which is the maximum Battle Effectiveness which Jessie can achieve in the `i`-th battle

### Sample Input

2 1 10 8 2 2 10 1 1 10

### Sample Output

82 101

### Sample Explanation

In the first battle, Jessie should use her second Pokémon for a Battle Effectiveness of 10×8 + 1×2 = 82. In the second battle, she should instead use her first Pokémon for a Battle Effectiveness of 1×1 + 10×10 = 101.

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 10.00s

**Memory Limit:** 64M

**Added:** Feb 01, 2019

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...