Rain on Your Parade

You're throwing a party in the garden of your villa by the sea. The party is a huge success and everyone is here. It is a warm, sunny evening, and a soothing wind carries fresh, salty air in from the sea. Then one of your guests, who works in weather forecasting, suddenly shouts: "I know that breeze! It means it is going to rain heavily in just a few minutes!" Your guests are all wearing their best clothes and really do not want to get wet.

You have set out a number of umbrellas around the garden, each of which can shelter one guest. The umbrellas are small, so no umbrella is ever shared: at most one guest may use each umbrella. Your guests also run at different speeds.

How many of your guests can reach an umbrella before the downpour begins?

Given the positions and speeds of all guests, the positions of the umbrellas, and the time left until it starts to rain, determine the maximum number of guests that can reach an umbrella. A guest can reach an umbrella if the guest's speed multiplied by the remaining time is at least the Euclidean distance between the guest and that umbrella. Each umbrella can be used by at most one guest.

The first line contains the number of test cases.

Each test case begins with a line containing the time $t$ in minutes until it starts to rain ($1 \le t \le 5$). The next line contains the number of guests $m$ ($1 \le m \le 3000$), followed by $m$ lines, each containing the $x$- and $y$-coordinates and the speed $s_i$ in units per minute of a guest as integers separated by spaces ($1 \le s_i \le 3000$). After the guests, a line contains the number of umbrellas $n$ ($1 \le n \le 3000$), followed by $n$ lines, each containing the integer coordinates of an umbrella separated by a space.

The absolute value of every coordinate is less than $10000$.

For each test case, first print a line "Scenario #i:", where $i$ is the test-case number starting at 1. Then print a line containing the maximum number of guests that can reach an umbrella before it starts to rain. Print a blank line between two consecutive scenarios.