18672번 - Cultivating Mars 다국어

Mars mission APOLLO was hit by a strong storm and astronaut Mark Watney got lost after being injured. Trying to save the rest of the crew, commander Melissa left Mark behind. The commander did so under the strong impression that Mark can never be alive after being hit. Luckily, Mark survived the injury and is now on his own on Mars. Unlike what people might think, Mark is really enjoying his time on Mars. The scenery is amazing and no body is there to annoy him.

After suffering for some time, Mark succeeded in contacting NASA and he is counting on their help to survive. He needs to stay alive on his own for 4 years until the next Mars mission rescues him. Mark likes it on Mars, but he has got some problems. The major one is food. He has food supplies that can keep him alive for only 5 months. Since he is a great botanist, Mark decided to grow crops on Mars. With NASA’s help, he figured out how to do so, but one problem remains. He discovered that the field where he will grow the crops has the shape of a convex polygon. He modeled the field as a convex polygon in a 2D coordinate system, where the field contains a number of cells. The cells of the field are all the integer points inside and on the boundaries of the polygon (including the vertices). Additionally, the vertices of the field are integer coordinates. He can grow crops in only one cell in the field; the problem is which cell to choose. Mark discovered that depending on different factors on Mars, some cells can grow crops faster than other cells. With his great scientific abilities, he figured out a formula for this. He was able to represent these factors by a pair of integers f = (a, b) and called it the growing factor. Depending on the growing factor f = (a, b), each cell (x, y) in the field will have a growing ability of g = a × x + b × y. Mark wants to choose the cell with the maximum growing ability. He might cultivate the field more than once, and each time he might encounter a different growing factor (according to the time of the year he is cultivating the field). Hence, for each different growing factor Mark will encounter (or expect to encounter), he wants to know the maximum growing ability he can get from the cells of the field. Mark sent all the information to NASA to help him. NASA hired you to help them find the maximum cell growing ability Mark can get for each given growing factor.

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100), followed by T test cases. The first line of each test case will contain two integers N (3 ≤ N ≤ 10, 000) and Q (1 ≤ Q ≤ 100, 000) separated by a single space, where N is the number of vertices of the convex polygon representing the field and Q is the number of different growing factors Mark expects to encounter for that field. The following N lines will each contain a pair of integers x and y separated by a single space (−10⁹ ≤ x, y ≤ 10⁹) representing the coordinates of the vertices. The vertices will be given in anti-clockwise order. It’s guaranteed that no three vertices will be on the same line. The following Q lines will each contain a pair of integers a and b (−10⁹ ≤ a, b ≤ 10⁹), separated by a single space, representing a growing factor.

For each growing factor, print one line which contains the maximum growing ability Mark can get for that growing factor on the cells of the given convex polygon (field).