Microsoft conducts 3 to 4 rounds to select freshers as SDE in their organization:

Online Round Technical Round 1 Technical Round 2 Technical-cum-HR Round

The online coding round consists of 2 coding questions with a time limit running between 1 hour to 1 hour 30 minutes. The question level varies, consisting of questions from domains such as Arrays, Strings, Single Linked Lists, and Double Linked Lists.

Seat Booking

You are given an integer N, denoting the number of seats in a cinema hall numbered from 1 to N. There are M groups, where B[i] denotes the number of persons in the i-th group. The persons from the same group want to sit together. If there are B[i] persons in the i-th group, then they would prefer to sit from L to R such that R - L + 1 = B[i]. A[i] denotes the cost of the i-th seat ticket. You have to help the cinema hall owner in making the maximum possible profit by assigning the seats to the groups in an optimal manner.

Constraints

• 1 <= N <= 500
• 1 <= M <= 13
• 1 <= A[i] <= 10^9
• 1 <= B[i] <= N
• B[1] + B[2] + B[3] + ... + B[m] <= N

Sample Input

N = 6 M = 2 A = [1, 7, 8, 2, 3, 9] B = [2, 1]

Sample Output

24