#1857. 文学
文学
文学
题目描述
标题: 文学 - Problem - QOJ.ac
The problem was used in the following contests:
巨酱和主席是一对好朋友。他们都很喜欢读书,经常一起阅读相关领域书籍,进行系统的学习。一天主席列出了一份列表,里面共 p 本书,其中不乏《约翰克里斯多夫》,《名人传》等名著。作为一名在文学上有很高修养的知名青年,巨酱打算用尽量少的时间把这份列表中的所有书籍都读完。
作为一名文化人,巨酱阅读书籍的方式也与一般人不同。他使用一种叫做“批量阅读”的阅读方式。首先他根据自己的喜好,对每本书给出了个参数 x,y,其中 i 本书的两个参数为 xi,yi。当然,由于巨酱独特的口味,可能有两本不同的书,它们的 x、y 参数均相同。而每次阅读的时候,他会设置三个系数 a, b, c,所有满足 ax+by≤c 的书籍都可以通过这次“批量阅读”读完,这次批量阅读总共需要 w 的时间。
现在,巨酱有 n 种 “批量阅读”的方案,第 i 种“批量阅读”三个参数为 ai,bi,ci,需要的时间为 wi。现在巨酱打算从这 n 种“批量阅读”中选出若干,使得巨酱可以用尽量少的时间读完所有的书。现在我们想知道,巨酱最少用多少时间?
输入格式
第一行两个正整数 n,p,分别表示“批量阅读”的方案数以及书的数量。
接下来 n 行,每行四个整数,其中第 i 行包含四个整数 ai,bi,ci,wi,表示第 i 种“批量阅读”的方案。
接下来 p 行,每行两个整数,其中第 i 行包含两个整数 xi,yi,表示第 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≤10。
对于 20% 的测试数据:n,p≤20。
在之后的 80% 中,均匀分布着一半数据,满足所有的 wi 均为 1。
对于 40% 的测试数据:n,p≤40。
对于 60% 的测试数据:n,p≤60。
对于 80% 的测试数据:n,p≤80。
对于 100% 的测试数据:n,p≤100, −106≤ai,bi,ci,xi,yi≤106, 0<wi≤106。
对于 100% 的测试数据:对于任何一种“批量阅读”方案,其 ai 与 bi 不会同时为 0。且不存在 i, j (i 不等于 j)使得 aibj=ajbi。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
8 10
1005 2452 333503 2326
-191 -163 -329185 9988
-636 181 -940525 4582
-16 -150 -122462 5121
128 -1155 -878399 9150
-345 -943 -869354 6220
77 -195 -198041 8231
-22 -27 -41256 3905
-1093 584
407 773
1359 -421
1540 215
-2795 1557
-898 661
1377 406
1587 -2778
1350 428
257 789
21839
样例 2
16 20
349 -22 -544979 9381
-81 -283 -259442 1339
38 229 -192373 2030
514 680 -909494 4821
-44 -444 -358272 1964
-270 -475 -560390 4498
15 -410 -325830 6911
-117 -103 -203759 3692
277 -918 -807434 1193
-23 -115 -98992 133
16 585 -460625 4903
-298 1051 -894533 2754
-529 2 -798264 5546
75 282 -254073 8170
307 -311 -537432 2065
-229 252 -412364 2698
-380 -777
-891 -664
932 650
90 798
40 -3199
-609 -739
-1549 199
-320 783
1508 -266
534 754
-70 3199
1267 -2938
649 731
1256 -495
2931 1283
-1571 -150
1510 263
205 -793
-1238 506
1407 380
22556