Description

Ju Jiang and the Chairman are a pair of good friends. They both enjoy reading, and often read books in related fields together for systematic learning. One day, the Chairman made a list of $p$ books, including famous works such as Jean-Christophe and Biographies of Famous People. As a well-known young man with strong literary taste, Ju Jiang plans to finish all the books on this list in as little time as possible.

As a man of culture, Ju Jiang reads differently from ordinary people. He uses a method called “batch reading”. First, based on his preferences, he assigns two parameters $x, y$ to each book; for book $i$, these parameters are $x_i, y_i$. Of course, due to Ju Jiang’s unique taste, two different books may have the same $x, y$ parameters.

Each time he reads, he sets three coefficients $a, b, c$. All books satisfying $a \times x + b \times y \leq c$ can be finished in this “batch reading”, and this batch reading takes a total time of $w$.

Now, Ju Jiang has $n$ “batch reading” plans. For plan $i$, the three parameters are $a_i, b_i, c_i$, and the required time is $w_i$. Ju Jiang wants to choose some of these $n$ plans so that he can finish all books in the least total time. You need to find the minimum time Ju Jiang needs.

Input Format

The first line contains two positive integers $n, p$, representing the number of “batch reading” plans and the number of books.

The next $n$ lines each contain four integers. The $i$-th line contains $a_i, b_i, c_i, w_i$, describing the $i$-th “batch reading” plan.

The next $p$ lines each contain two integers. The $i$-th line contains $x_i, y_i$, describing the parameters of the $i$-th book.

Output Format

Output one integer in one line, representing the minimum required time. If it is impossible to finish all the books no matter what, output $-1$.

4 3
-1 0 0 10
-1 -1 -1 2
-1 1 -1 2
-1 -2 -1 1
0 2
0 -2
1 0

3

Hint

For $100\%$ of the testdata: $1 \leq n, p \leq 100$, $-10^6 \leq a_i, b_i, c_i, x_i, y_i \leq 10^6$, $0 < w_i \leq 10^6$. It is guaranteed that for any “batch reading” plan, $a_i$ and $b_i$ are not both $0$. Also, there do not exist $i, j$ ($i \ne j$) such that $a_i \times b_j = a_j \times b_i$.

Translated by ChatGPT 5