P5928 [Tsinghua Training 2014] Literature

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.

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 one integer in one line, representing the minimum required time. If it is impossible to finish all the books no matter what, output $-1$.

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