D. Convex
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$N$$$ pairs of integers $$$m_i,b_i$$$ representing lines in the form of $$$y = m_ix + b_i$$$.

You are also given a set of integers $$$S$$$ of size $$$M.$$$

$$$$$$ f(x) = \begin{cases} \text{the minimum of all } N \text{ lines} & x \in S \\ \text{the maximum of all } N \text{ lines} & x \notin S \end{cases} $$$$$$

Determine if $$$f(x)$$$ is convex$$$^{*}$$$.

$$$^{*}$$$ A function is convex if slopes are non-decreasing over all real $$$x$$$. In other words, a function is convex if, for any real $$$x_1 \lt x_2 \lt x_3$$$, the slope from $$$x_1$$$ to $$$x_2$$$ is $$$\le$$$ the slope from $$$x_2$$$ to $$$x_3$$$.

Input

The first line consists of an integer $$$t$$$ ($$$1 \le t \le 100$$$), the number of test cases.

The first line of each test case consists of two integers $$$N$$$ ($$$1 \le N \le 10^5$$$) and $$$M$$$ ($$$0 \le M \le 10^5$$$), the number of lines given, and the size of set $$$S$$$, respectively.

The next $$$N$$$ lines each consist of a pair of integers $$$m_i,b_i$$$ ($$$-10^9 \le m_i,b_i \le 10^9$$$), describing a line.

The next line consists of $$$S_1,S_2,...,S_M$$$ ($$$-10^9 \le S_i \le 10^9$$$), describing the set $$$S$$$.

The sum of $$$N$$$ and the sum of $$$M$$$ over all $$$t$$$ test cases does not exceed $$$10^5$$$.

—

Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Tests $$$1-20$$$ satisfy no additional constraints.

Output

For each test case, output "YES" if $$$f(x)$$$ is convex; otherwise, output "NO."

Example
Input
4
3 0
1 2
-1 4
4 -1
3 1
1 2
-1 4
4 -1
1
3 2
1 2
-1 4
4 -1
1 -2
2 2
1 2
1 2
1 -2
Output
YES
YES
NO
YES
Note

Visualization for sample test:

Lines used in tests 1-3
Lines used in test 4

—

Problem Idea: Buzzy2

Problem Preparation: Buzzy2

Occurrences: Novice D