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栋建筑全部拆除了。