**CodeInvicta: CINVIT03: EDITORIAL**

**Problem**

**Knapsack**

**Problem:**

Chef is having a Knapsack which contains Mangoes of different weight. Let’s take an array knap[] of size N which contains {knap[0], knap[1], ……………, knap[n−1]}, where knap[i] denotes the weight of a mango ii. Also, he wants to sell all these mangoes by packing all those in a different Carry bag. The number of mangoes each Carry bag can hold is given in cb[] array of size M. cb[i] denotes the number of mangoes can a particular Carry bag carry. So, Chef will keep exactly cb[i] the number of mangoes in this Carry_bag.

NoteNote that {cb[0]+ cb[1]+ …… +cb[m−1] = N}

At the same time, he wants to fill the Carry bag in a different manner. He wants to fill all the Carry bag in such a way that the total sum of minimum and maximum weight of mangoes present in every Carry bag after packing is maximum. Chef wants you to find the required sum.

## Input

The first line contains two integers Nand M (1≤N≤105;1≤M≤N) — the size of knap[] array and the size of cb[] array.

The second line contains N integers a1, a2, …, an($1 ≤ ai ≤ 10^5) — the weight of mangoes present in knapsack.

The third line contains MM integers c1, c2, …, cM ($1 ≤ ci ≤ n) — number of mangoes Chef will keep in each Carry bag.

## Output

Print a single integer — the maximum sum.

## Sample Input

```
4 2
1 10 6 15
1 3
```

## Sample Output

```
41
```

## Explanation

The chef should keep the greatest weight in the first Carry bag {15}. So, 15 is the minimum and 15 is the maximum & remaining unit of mangoes kept in the second Carry bag {1,6,10}. So 1 is the minimum and 10 is the maximum. So, the total sum = 15+15+1+10 = 41 which is the maximum.

## Solution

```
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int arr[]=new int[n+1]; //We are taking knapsack array as arr[]
int wt[]=new int[m+1]; // Here we are taking cb[] array as wt[]
//taking user input
for(int i=1;i<=n;i++){
arr[i]=sc.nextInt();
}
for(int i=1;i<=m;i++){
wt[i]=sc.nextInt();
}
//Here we have sorted both the Array
Arrays.sort(arr,1,n+1);
Arrays.sort(wt,1,m+1);
/*Here Result is initialized...We have taken 2 pointers i & j, where i is denoting 1 and j is denoting n initially.
p is the pointer which denoting in wt[]...First we will make sure to fill the requirements of carry_bag having capacity of 1
mango..so while p is less than equals to m because m is maximum number of quantity... wt[p] are which basically represent the requirements of carry_bag.
if requirement is 1 then we would add in the result (res).. In arr[j] , j represents maximum weight of mango available..
we have to keep maximum in all carry bag which quantity is 1....so we will multiply by 2 in result...*/
int res = 0;
int i = 1;
int j = n;
int p = 1;
while(p <= m && wt[p] == 1){
res += 2 * arr[j] ;
j-- ;
p++;
}
//Now we will starting from m because first we have to fill max carry bag
for(int q=m;q>=p;q--)
{
res += arr[j] + arr[i];
j-- ; i++ ; wt[q] -= 2;
while(wt[q] > 0){
i++ ; wt[q]--;
}
}
System.out.println(res);
}
}
```