H. Rocks & Fossils Kit - 200+ Piece Set
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Jackson School of Geosciences recently bought a Rocks & Fossils Kit – 200+ Piece Set Includes Geodes, Real Fossils, Rose Quartz, Jasper, Aventurine & Many More Rocks, Crystals & Gemstones! The school would like to give out the rocks to faculty. To do so, they lay out the rocks in a line. Each rock has some value $$$c_i$$$.

However, as geologists specializing in different rock types, the faculty members have very particular requirements as to what rocks they are willing to take. In particular, each geologist will only take rocks starting at some position $$$a_j$$$, and then continue taking rocks from indices $$$a_j+1, a_j+2,...$$$ until one of the following happens:

  • The rock at the new index has already been taken.
  • They reach the end of the line.
  • They satisfy their collection, that is, the total value of the rocks they've taken so far is greater than or equal to some value $$$k_j$$$.

The faculty members line up to take turns choosing rocks. JSC wants to know: what's the maximum number of collections that can be satisfied, if they choose the optimal order in which the faculty members line up?

Input

The first line contains two integers $$$1 \le N \le 10^5$$$ and $$$1 \le M \le 10^5$$$, corresponding to the number of rocks and the number of faculty members, respectively.

The next line contains $$$N$$$ integers $$$c_1,...,c_N$$$, where $$$c_i$$$ represents the value of the $$$i$$$th rock. $$$(1 \le c_i \le 10^9)$$$

The third line contains $$$M$$$ integers $$$a_1,...,a_M$$$, where the $$$j$$$th faculty member takes rocks starting at index $$$a_j$$$. $$$(1 \le a_j \le N)$$$

The fourth and final line contains $$$M$$$ integers $$$k_1,...k_M$$$, where the $$$j$$$th faculty member satisfies their rock collection if the total value of the rocks they collect is greater than or equal to $$$k_j$$$. $$$(1 \le k_j \le 10^9)$$$

Output

Output one integer: the maximum number of collections that can be satisfied.

Examples
Input
7 4
1 5 3 1 2 3 1
1 3 4 5
5 6 5 6
Output
2
Input
7 3
1 5 3 3 2 3 1
1 2 5
10 1 3
Output
2
Note

In the first example, one possible ordering of faculty members is [1, 3, 2, 4]:

  • The first faculty member takes the 1st and 2nd rocks to satisfy their collection ($$$1 + 5 \ge 5$$$).
  • The third faculty member takes the 4th, 5th, and 6th rocks to satisfy their collection ($$$1 + 2 + 3 \ge 6$$$).
  • The second faculty member takes the 3rd rock, but the 4th rock has already been taken, so they can't satisfy their collection ($$$3 \lt 5$$$).
  • The fourth faculty member can't satisfy their collection because the 5th rock has already been taken. ($$$0 \lt 6$$$)
Note that other orderings are possible, but none can satisfy more than two collections.