## DMPG '19 G1 - Camera Calibration Challenge

View as PDF

Points: 12 (partial)
Time limit: 2.5s
Memory limit: 128M

Authors:
Problem type

One of the recommendations made this year was for Kirito to make a pre-recorded opening speech for the DMPG that would be played at the satellite sites.

To achieve this, Kirito borrowed AvaLovelace's camera and digital art expertise. While fooling around with learning about the camera's features, he realized that he accidentally messed up the camera's exposure correction! Panicking, he recalls what she taught him about exposure:

A photo can be represented as a grid of by pixels, and the pixel in row and column has a brightness , which can be any real number from to inclusive. If you average the brightnesses of all the pixels in a typical image, the result is called the proper exposure.

Most digital cameras have an exposure correction feature. By choosing a correction constant and multiplying all the pixel brightnesses in an image by , a darker or brighter image can be obtained. When applying a correction constant, if any pixel brightnesses become greater than 1, those values are "clipped" and reduced to 1.

Armed with this knowledge, Kirito knows that to re-calibrate the camera, he has to answer queries:

What is the correction constant necessary for the proper exposure of this image to be ?

Since he would prefer not to work with floating-point numbers, for each query , he would like to know the smallest integer such that applying the correction constant to the image results in a proper exposure greater than or equal to .

#### Input Specification

The first line of input will contain space separated integers, and .
The next lines will each contain space-separated integers, the pixel brightnesses multiplied by .
This will be followed by a single integer, .
The next integers will each contain a single integer, multiplied by .

#### Output Specification

lines, where the th line contains the smallest possible that will result in a proper exposure greater than or equal to .

#### Sample Input 1

2 3
360000 304000 120000
408000 312000 960000
1
480000

#### Sample Output 1

1250000

#### Sample Input 2

2 3
480000 580000 560000
380000 400000 480000
3
120000
480000
360000

#### Sample Output 2

250000
1000000
750000