Revision en1, by Dinocoder, 2023-10-03 11:16:41

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 ith group. The persons from the same group want to sit together. A[i] denotes the cost of the ith seat ticket. You have to help the cinema hall owner make the maximum possible profit by assigning the seats to the groups optimally.

Calculate the maximum profit the cinema hall owner can make through an optimal seating arrangement.

Parameters description

• N: Represents the number of seats in the cinema hall

• M: Represents the number of groups visiting the cinema hall

• A: Represents the array A, where A[i] represents the cost of the ith seat ticket

B: Represents the array B, where B[i] represents the number of persons in the ith group

Input format

The first line contains a positive integer N denoting the size of the array A. The second line contains a positive integer M denoting the size of the array B.

The third line contains N positive space-separated integers denoting elements of the array A.

The fourth line contains M positive space-separated integers denoting elements of the array B.

Output format

Print a single integer denoting the maximum profit the cinema hall owner can make through an optimal seating arrangement.

Constraints

1 <= N <= 5 * 10 ^ 2

1 <= M <= 13

1 <= A_{i} <= 10 ^ 9

1 <= B_{i} <= N

B_{1} + B_{2} + B_{3} +.......+B M <=N

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 Dinocoder 2023-10-03 11:16:41 1525 Initial revision (published)