Renovation

题意翻译

有m个建筑，每个建筑拆除需要pi代价，装修需要bi代价。有n个月，每个月预算ai。每个月可以拆除若干建筑，但为了欺骗市民是装修，需要bj≤ai才能拆除j建筑。拆除可以用到之前存的预算。求最多拆除多少个建筑。n,m≤1e5

题目描述

The mayor of the Berland city S sees the beauty differently than other city-dwellers. In particular, he does not understand at all, how antique houses can be nice-looking. So the mayor wants to demolish all ancient buildings in the city. The city S is going to host the football championship very soon. In order to make the city beautiful, every month the Berland government provides mayor a money tranche. The money has to be spent on ancient buildings renovation. There are $ n $ months before the championship and the $ i $ -th month tranche equals to $ a_{i} $ burles. The city S has $ m $ antique buildings and the renovation cost of the $ j $ -th building is $ b_{j} $ burles. The mayor has his own plans for spending the money. As he doesn't like antique buildings he wants to demolish as much of them as possible. For the $ j $ -th building he calculated its demolishing cost $ p_{j} $ . The mayor decided to act according to the following plan. Each month he chooses several (possibly zero) of $ m $ buildings to demolish in such a way that renovation cost of each of them separately is not greater than the money tranche $ a_{i} $ of this month ( $ b_{j}<=a_{i} $ ) — it will allow to deceive city-dwellers that exactly this building will be renovated. Then the mayor has to demolish all selected buildings during the current month as otherwise the dwellers will realize the deception and the plan will fail. Definitely the total demolishing cost can not exceed amount of money the mayor currently has. The mayor is not obliged to spend all the money on demolishing. If some money is left, the mayor puts it to the bank account and can use it in any subsequent month. Moreover, at any month he may choose not to demolish any buildings at all (in this case all the tranche will remain untouched and will be saved in the bank). Your task is to calculate the maximal number of buildings the mayor can demolish.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ m $ $ (1<=n,m<=100000) $ — the number of months before the championship and the number of ancient buildings in the city S. The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ), where $ a_{i} $ is the tranche of the $ i $ -th month. The third line contains $ m $ integers $ b_{1},b_{2},...,b_{m} $ ( $ 1<=b_{j}<=10^{9} $ ), where $ b_{j} $ is renovation cost of the $ j $ -th building. The fourth line contains $ m $ integers $ p_{1},p_{2},...,p_{m} $ ( $ 1<=p_{j}<=10^{9} $ ), where $ p_{j} $ is the demolishing cost of the $ j $ -th building.

输出格式

Output single integer — the maximal number of buildings the mayor can demolish.

输入输出样例

输入样例 #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

说明

In the third example the mayor acts as follows. In the first month he obtains $ 6 $ burles tranche and demolishes buildings $ #2 $ (renovation cost $ 6 $ , demolishing cost $ 4 $ ) and $ #4 $ (renovation cost $ 5 $ , demolishing cost $ 2 $ ). He spends all the money on it. After getting the second month tranche of $ 3 $ burles, the mayor selects only building $ #1 $ (renovation cost $ 3 $ , demolishing cost $ 1 $ ) for demolishing. As a result, he saves $ 2 $ burles for the next months. In the third month he gets $ 2 $ burle tranche, but decides not to demolish any buildings at all. As a result, he has $ 2+2=4 $ burles in the bank. This reserve will be spent on the fourth month together with the $ 4 $ -th tranche for demolishing of houses $ #3 $ and $ #5 $ (renovation cost is $ 4 $ for each, demolishing costs are $ 3 $ and $ 5 $ correspondingly). After this month his budget is empty. Finally, after getting the last tranche of $ 3 $ burles, the mayor demolishes building $ #6 $ (renovation cost $ 2 $ , demolishing cost $ 3 $ ). As it can be seen, he demolished all $ 6 $ buildings.

题意翻译

有m个建筑，每个建筑拆除需要pi代价，装修需要bi代价。有n个月，每个月预算ai。每个月可以拆除若干建筑，但为了欺骗市民是装修，需要bj≤ai才能拆除j建筑。拆除可以用到之前存的预算。求最多拆除多少个建筑。n,m≤1e5