Ju-Jiang and the Chairman are good friends. They both love reading and often read books in related fields together to engage in systematic learning. One day, the Chairman listed $p$ books, including classics such as Jean-Christophe and Celebrities. As a well-known young man with high literary cultivation, Ju-Jiang intends to finish reading all the books on this list in as little time as possible.
As a cultured person, Ju-Jiang's way of reading books is different from others. He uses a method called "batch reading." First, based on his preferences, he assigns two parameters $x$ and $y$ to each book, where the two parameters for the $i$-th book are $x_i, y_i$. Of course, due to Ju-Jiang's unique taste, there may be two different books that have the same $x$ and $y$ parameters. Each time he reads, he sets three coefficients $a, b, c$, and all books satisfying $ax+by \leq c$ can be finished through this "batch reading" session, which takes a total time of $w$.
Now, Ju-Jiang has $n$ types of "batch reading" plans. The $i$-th "batch reading" plan has three parameters $a_i, b_i, c_i$ and requires time $w_i$. Ju-Jiang intends to select a subset of these $n$ "batch reading" plans such that he can finish reading all the books in the minimum amount of time. We want to know, what is the minimum time required for Ju-Jiang?
Input
The first line contains two positive integers $n$ and $p$, representing the number of "batch reading" plans and the number of books, respectively.
The next $n$ lines each contain four integers. The $i$-th line contains four integers $a_i, b_i, c_i, w_i$, representing the $i$-th "batch reading" plan.
The next $p$ lines each contain two integers. The $i$-th line contains two integers $x_i, y_i$, representing the parameters of the $i$-th book.
Output
Output a single integer representing the minimum time required. If it is impossible to finish all the books regardless of the choices, output $-1$.
Examples
Examples
input
4 3 -1 0 0 10 -1 -1 -1 2 -1 1 -1 2 -1 -2 -1 1 0 2 0 -2 1 0
output
3
input
6 10 -16 48 -2720 1 -23 -6 -2241 1 -12 -12 -1320 1 -25 22 -2607 1 -19 -54 -3105 1 95 2 2661 1 -190 -60 -105 170 77 -31 99 -6 81 29 -150 -131 27 48 93 17 176 -94 29 -47
output
3
input
7 10 -12 -12 -1320 8783 -19 -54 -3105 6072 -23 -6 -2241 2540 -8 11 -957 3013 -17 11 -1749 4955 -16 48 -2720 2616 95 2 2661 1013 -190 -60 -105 170 77 -31 88 -23 81 29 -150 -131 27 48 93 17 99 -6 29 -47
output
12638
input
16 20 6 -79 -3630 1 -16 47 -2689 1 15 104 -4453 1 -11 -12 -1239 1 38 -47 -3950 1 -13 -30 -1923 1 -18 -3 -1764 1 -6 -24 -1314 1 -17 11 -1749 1 5 4 -535 1 19 4 -1865 1 -1 0 -93 1 12 16 -1412 1 -5 -3 -516 1 -8 11 -957 1 0 1 -47 1 93 17 99 -6 -99 4 -75 -32 4 -199 51 42 88 -23 183 78 96 12 93 18 27 48 77 -31 30 -47 -95 -15 -163 -114 -100 172 -91 -20 29 -47 81 29 -52 42
output
7
input
17 20 15 104 -4453 618 -16 47 -2689 430 0 1 -47 2937 -1 -2 -129 96 -18 -3 -1764 9878 6 -79 -3630 2789 19 4 -1865 7887 12 16 -1412 5215 -8 11 -957 9861 -17 11 -1749 7235 38 -47 -3950 122 -6 -24 -1314 3669 -13 -30 -1923 7697 -5 -3 -516 261 -10 -10 -1100 1359 -1 0 -93 1569 5 4 -535 2731 93 17 88 -23 -52 42 -91 -20 4 -199 81 29 77 -31 99 -6 96 12 93 18 51 42 30 -47 29 -47 -99 4 -163 -114 -100 172 -95 -15 -75 -32 91 19 27 48
output
14282
Constraints
For 10% of the test data: $n, p \leq 10$.
For 20% of the test data: $n, p \leq 20$.
In the subsequent 80%, half of the data is uniformly distributed such that all $w_i = 1$.
For 40% of the test data: $n, p \leq 40$.
For 60% of the test data: $n, p \leq 60$.
For 80% of the test data: $n, p \leq 80$.
For 100% of the test data: $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$.
For 100% of the test data: For any "batch reading" plan, $a_i$ and $b_i$ are not both $0$. Furthermore, there exist no $i, j$ ($i \neq j$) such that $a_i b_j = a_j b_i$.