Maximize Satisfied Bites

Facer bought n cakes today. Unfortunately, some lazy people from the information group discovered the cakes and persuaded him to share. Facer promised to give everyone one bite from a single cake. However, he measured each person’s mouth size, which determines the exact amount of cake they can eat.

Facer can cut a cake arbitrarily without wasting any cake, but he cannot join pieces from different cakes, and he will not give any person more than one piece. In other words, each person’s serving must come as a contiguous piece from exactly one cake. Given the sizes of the cakes and each person’s required bite (mouth size), determine the maximum number of people Facer can fully satisfy.

The condition for each cake is that the sum of the bite sizes taken from it cannot exceed its total size. Note that a cake may be cut into many pieces if needed.

The problem can be formulated as follows. Suppose you have n cakes with sizes \(a_1, a_2, \dots, a_n\) and m people with mouth sizes \(b_1, b_2, \dots, b_m\). Find the maximum number of people for which you can assign a piece from some cake so that for each cake, the sum of assigned bite sizes does not exceed its size.

Input Format (see below)

inputFormat

The first line contains two integers n and m (number of cakes and number of people). The second line contains n integers: the sizes of the cakes \(a_1, a_2, \dots, a_n\). The third line contains m integers: the required bite sizes for each person \(b_1, b_2, \dots, b_m\).

outputFormat

Output a single integer, the maximum number of people that can be satisfied.

sample

2 3
5 8
4 4 3

3