Minimizing Batch Reading Time

Gi Jiang and Chairman are good friends who love reading books. One day, Chairman listed p books, including classics such as Jean-Christophe and Famous Lives. Gi Jiang, a man of literary taste, wants to read all these books in as little time as possible.

Gi Jiang uses a "batch reading" method. For each book, he assigns two parameters \(x_i\) and \(y_i\) (note that different books can have the same pair). In one batch reading session he sets three coefficients \(a, b, c\) so that any book satisfying the inequality:

[ a \times x + b \times y \le c ]

can be read during that session. Each session takes a fixed time \(w\).

Now, Gi Jiang has n different batch reading schemes. The \(i\)th scheme is characterized by parameters \(a_i, b_i, c_i\) and has a time cost \(w_i\). He can select some of these schemes (each at most once) such that every one of the p books is read by at least one chosen session. Your task is to determine the minimum total time needed to read all the books. If it is impossible to cover all books, output -1.

Note: The inequality is in the \(\le\) form, meaning equality is permitted.

inputFormat

The first line contains two integers \(p\) and \(n\), the number of books and the number of batch reading schemes, respectively.

The next \(p\) lines each contain two integers \(x_i\) and \(y_i\) — the parameters for the \(i\)th book.

The following \(n\) lines each contain four integers \(a_i, b_i, c_i, w_i\) representing the parameters and time cost of the \(i\)th batch reading scheme.

Constraints: \(1 \le p \le 15\) and \(1 \le n \le 15\).

outputFormat

Output a single integer, the minimum total time required to cover (read) all books. If it is impossible with the given schemes, output -1.

sample

3 3
1 2
2 1
3 3
1 1 4 5
0 1 3 2
2 2 12 10

2