Diamond Dealer

Mr. Chou is a diamond dealer in a two-dimensional world. To be a successful businessman, he must know the exact value of the (two-dimensional) diamonds he trades. Mr. Chou is tired of computing these values by hand, so you must write a program that does it for him.

The value of a diamond is determined by the smoothness of its surface. Smoothness depends on the number of faces on the surface: the more faces, the smoother the surface. If the surface has dents (shown in red in the figure), the value of the diamond decreases.

A diamond is given as a simple polygon defined by its vertices. Each concave vertex of the polygon (a vertex whose interior angle is greater than 180 degrees) is a dent, and each edge of the polygon is a face. A face is considered to be in a dent if at least one of its two endpoints is a concave vertex.

Let $a$ be the number of dents and let $b$ be the number of faces that are not in any dent. The value $v$ of the diamond is

$v = -a \cdot p + b \cdot q,$

where $p$ is the penalty for a dent and $q$ is the value of a face. If $v$ is negative, the diamond is worthless and its value is $0$.

The first line contains the number of test cases $T$.

Each test case consists of:

• One line with three integers $p$, $q$, and $m$: the penalty for a dent ($0 \le p \le 100$), the value of a face ($0 \le q \le 100$), and the number of vertices describing the diamond ($3 \le m \le 30$).
• $m$ lines, each with two integers $x_i$ and $y_i$ ($-1000 \le x_i, y_i \le 1000$), giving the vertices of the polygon in clockwise order: $(x_0, y_0) - (x_1, y_1) - \cdots - (x_{m-1}, y_{m-1}) - (x_0, y_0)$.

No three vertices of a single diamond are collinear.

For each test case, print a single line containing one integer: the value of the diamond.