← 返回题目列表

Codeforces · 883/J

J. 装修

中文机器翻译题面 查看原题

Berland市S市长对美丽的看法与其他城市居民不同。尤其是他根本不明白,古色古香的房子怎么能好看。所以市长要拆除城里所有的古建筑。

S市即将举办足球锦标赛。为了让这座城市变得美丽,贝尔兰政府每个月都会向市长提供一笔资金。这些钱都得花在古建筑修缮上。

距离冠军还有n个月,第i个月的份额等于ai burles。 S市有m栋仿古建筑,第j栋建筑的装修费用为bj burles。

市长对于这笔钱有他自己的计划。由于他不喜欢古董建筑,他想尽可能多地拆除它们。对于第 j 栋建筑,他计算了其拆除成本 pj。

市长决定按照以下计划行事。

每个月他都会选择 m 栋建筑中的几栋(可能是零栋)进行拆除,并且每栋建筑的改造费用不大于本月的资金 ai(bj ≤ ai)——这样可以欺骗城市居民,就是这栋建筑将被改造。

那么市长必须在当月内拆除所有选定的建筑物,否则居民将意识到欺骗,计划就会失败。拆除总费用绝对不能超过市长目前拥有的资金。市长没有义务把所有的钱都花在拆除上。如果剩下一些钱,市长会将其存入银行帐户,并可以在随后的任何一个月使用。此外,在任何月份,他都可以选择根本不拆除任何建筑物(在这种情况下,所有部分将保持不变并保存在银行中)。

你的任务是计算市长可以拆除的最大建筑物数量。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100 000)——距离冠军还有多少个月以及 S 市的古建筑数量。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109),其中 ai 是第 i 个月的档次。

第三行包含 m 个整数 b1, b2, ..., bm (1 ≤ bj ≤ 109),其中 bj 是第 j 栋建筑物的装修成本。

第四行包含 m 个整数 p1, p2, ..., pm (1 ≤ pj ≤ 109),其中 pj 是第 j 栋建筑物的拆除成本。

输出

输出单个整数——市长可以拆除的最大建筑物数量。

示例

输入 #1

2 3
2 4
6 2 3
1 3 2

输出 #1

2

输入 #2

3 5
5 3 1
5 2 9 1 10
4 2 1 3 10

输出 #2

3

输入 #3

5 6
6 3 2 4 3
3 6 4 5 4 2
1 4 3 2 5 3

输出 #3

6

注意

在第三个示例中,市长的行为如下。

在第一个月,他获得了 6 个 burles 批次并拆除了#2 建筑物(装修成本 6,拆除成本 4)和#4(装修成本 5,拆除成本 2)。他把所有的钱都花在了上面。

在获得第二个月的 3 笔补助后,市长仅选择 1 号楼(装修成本 3,拆除成本 1)进行拆除。结果,他为接下来的几个月节省了 2 个毛刺。

在第三个月,他获得了 2 批毛刺,但决定根本不拆除任何建筑物。结果,他的银行里有 2 + 2 = 4 个 burles。

该储备金将在第四个月与第四笔款项一起用于拆除#3和#5房屋(装修费用为4,拆除费用相应为3和5)。这个月之后他的预算就空了。

最后,在获得最后一批 3 块钱后,市长拆除了 6 号楼(装修费用 2,拆除费用 3)。

可以看出,他把6栋建筑全部拆除了。