3700: 水果加工(第六轮02)
题目描述
某水果公司有n片果园，第i片果园上种着ai 吨水果，公司有2个加工基地来加工这 些水果，并且，公司雇佣了运输公司将果园上的水果送往各个基地。
水果加工的流程如下：
- 运输公司将各片果园的水果输往各个基地。
- 所有水果均运输完毕后，基地开始加工。
从第j片果园运输水果到第i个基地的运输成本为每吨dij 小时。假设第j片果园往第 i个基地运送了wij 吨水果，则运输时间为Max(dij × wij)(1 ≤ i ≤ 2,1 ≤ j ≤ n)。
第i个基地有bi 台机器来加工水果，并且第i个基地需要cij 台机器组成的生产线来 加工第j片果园的水果，加工时间为每吨uij 分钟。假设第j片果园往第i个基地运送 了wij 吨水果，则加工时间为Max(uij × wij )(1 ≤ i ≤ 2,1 ≤ j ≤ n)。
完成水果加工所需要的总时间为T = Max(dij × wij) + Max(uij × wij )(1 ≤ i ≤ 2,1 ≤ j ≤ n)
合法的加工方案应该满足：
- 加工基地对于每片果园里的水果最多只分配 1 条生产线。
- 对于基地i，基地中所有生产线上的机器数量和不超过bi， 即Σj cij ≤ bi 。
数据保证存在满足加工流程的方案。。
问合法完成水果加工所需要的最小时间是多少，请输出最少时间。
输入
第 1 行 1个整数n，表示果园数量。
第 2 行n个整数，第i个整数ai 表示第i片果园待加工的水果数量。
第 3 行 2个整数b1, b2，分别表示基地 1 的机器数量和基地 2 的机器数量。
第 4,5 行每行n个整数，第4 行第j个数表示c1j，第 5 行第j个数表示c2j，如题意所 示。
第 6,7 行每行n个整数，第 6 行第j个数表示d1j，第 7 行第j个数表示d2j，如题意 所示。
第 8,9 行每行n个整数，第8 行第j个数表示u1j ，第 9 行第j个数表示u2j，如题意 所示。
输出
如题意所示，
一个整数，表示完成加工所需要的最少时间。
样例输入 复制
2
1 2
2 2
2 1
1 1
1 1
2 2
1 2
3 3样例输出 复制
5提示
【样例 1 输入】
2
1 2
2 2
2 1
1 1
1 1
2 2
1 2
3 3
【样例 1 输出】
5
【样例 1 说明】
对于样例，可能存在的所有加工流程如下：
- 果园 1 运输 1 吨水果到基地 1，果园 2 运输 2 吨水果到基地 2：运输时间 +加 工时间=4+6=10
- 果园 1 运输 1 吨水果到基地 2，果园 2 运输 2 吨水果到基地 1：运输时间 +加 工时间=2+4=6
- 果园 1 运输 1 吨水果到基地 2， 果园 2 运输 1 吨水果到基地 1， 果园 2 运输 1 吨水果到基地 2：运输时间 +加工时间=2+3=5
- 果园 2 运输 1 吨水果到基地 2，果园 2 运输 2 吨水果到基地 2：运输时间 +加 工时间=2+6=8。
【样例 2 输入】
7
1 2 2 1 1 2 1
7 9
3 3 2 1 4 3 4
4 4 2 3 1 1 3
781550533 441252986 654935771 900501247 867479246 245540480 456135532
846397701 695724977 523220951 27842148 449132477 211583261 181560377
991369089 114605201 342087285 13363813 508839856 339298729 767970261
73641538 118557921 689788733 265873121 703327135 879314301 551558747
【样例 2 输出】
2805070504
【样例 2 说明】
该样例作为大样例。
【样例 3 输入】
29
2 1 1 1 1 1 1 1 1 2 2 2 1 1 1 2 1 1 1 1 1 1 3 2 1 1 2 2 2
40 40
3 1 4 5 4 2 2 1 1 4 3 3 5 2 4 1 5 1 1 2 2 5 2 5 5 1 2 5 5
2 5 2 4 5 1 2 1 5 2 1 3 1 3 2 2 4 4 3 4 5 2 2 1 3 3 2 4 2
37778074 56667569 75555653 94444541 113333847 132223137 151111691
170000707 188889165 226667028 264445111 302222824 321111589 340000213
358889171 396667581 415556446 434445051 453333487 472222288 491111237
510000321 566666773 604444766 623333780 642222739 680000536 71777861
755556088
584 152 783 181 563 398 674 701 219 895 82 929 831 273 231 690 380 741 158
966 71 902 660 96 454 57 552 145 640
642 896 454 230 303 129 676 225 647 628 347 175 792 203 113 732 113 459 438
279 347 195 363 341 246 762 514 941 750
736666350 717777659 698888334 679999573 661110775 642221755 623332360
604444403 585555338 547777279 509999196 472221713 453332898 434443608
415555169 377777190 358888238 339999678 321110305 302221275 283332942
264443436 207777350 169999380 151110649 132221494 94444432 56666645
18888623
【样例 3 输出】
1038888486
【样例 3 说明】
该样例作为更大的大样例。
