巨酱和主席是一对好朋友。他们都很喜欢读书，经常一起阅读相关领域书籍，进行系统的学习。一天主席列出了一份列表，里面共 $p$ 本书，其中不乏《约翰克里斯多夫》，《名人传》等名著。作为一名在文学上有很高修养的知名青年，巨酱打算用尽量少的时间把这份列表中的所有书籍都读完。

作为一名文化人，巨酱阅读书籍的方式也与一般人不同。他使用一种叫做“批量阅读”的阅读方式。首先他根据自己的喜好，对每本书给出了个参数 $x, y$，其中 $i$ 本书的两个参数为 $x_i, y_i$。当然，由于巨酱独特的口味，可能有两本不同的书，它们的 $x$、$y$ 参数均相同。而每次阅读的时候，他会设置三个系数 $a$, $b$, $c$，所有满足 $ax+by \leq c$ 的书籍都可以通过这次“批量阅读”读完，这次批量阅读总共需要 $w$ 的时间。

现在，巨酱有 $n$ 种 “批量阅读”的方案，第 $i$ 种“批量阅读”三个参数为 $a_i, b_i, c_i$，需要的时间为 $w_i$。现在巨酱打算从这 $n$ 种“批量阅读”中选出若干，使得巨酱可以用尽量少的时间读完所有的书。现在我们想知道，巨酱最少用多少时间？

输入格式

第一行两个正整数 $n, p$，分别表示“批量阅读”的方案数以及书的数量。

接下来 $n$ 行，每行四个整数，其中第 $i$ 行包含四个整数 $a_i, b_i, c_i, w_i$，表示第 $i$ 种“批量阅读”的方案。

接下来 $p$ 行，每行两个整数，其中第 $i$ 行包含两个整数 $x_i, y_i$，表示第 $i$ 本书的参数。

输出格式

一行一个整数，表示最少需要的时间。若无论如何也无法读完全部书籍，则输出 $-1$。

样例一

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

限制与约定

对于 10% 的测试数据：$n, p \leq 10$。

对于 20% 的测试数据：$n, p \leq 20$。

在之后的 80% 中，均匀分布着一半数据，满足所有的 $w_i$ 均为 $1$。

对于 40% 的测试数据：$n, p \leq 40$。

对于 60% 的测试数据：$n, p \leq 60$。

对于 80% 的测试数据：$n, p \leq 80$。

对于 100% 的测试数据：$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$。

对于 100% 的测试数据：对于任何一种“批量阅读”方案，其 $a_i$ 与 $b_i$ 不会同时为 $0$。且不存在 $i$, $j$ （$i$ 不等于 $j$）使得 $a_i b_j= a_jb_i$。

时间限制：$2\texttt{s}$

空间限制：$256\texttt{MB}$

来源

中国国家队清华集训2014~2015 Day 4 - By 王若松

下载

样例数据下载