Beautiful Squares (Hackwithinfy)

Problem 2 Hackwithinfy 2021 Solution

Akshat is a 4-year old boy who loves playing with squares. He has N squares and each square has a side length of S i.

You asked Akshat to create K pyramids of square using all the N squares he has such that the count of squares in i th (1<=i<=K) pyramid is C i.

A pyramid of squares is denoted by a stack of squares in which the lowest most squares have the largest side length and the length of the sides of squares decreases as you move up.

The beauty of the structure is defined as the sum of side length of the topmost square and the lowermost square in all the K pyramids.

Akshat wants to figure out what is the maximum beauty of a structure he can create?

Note: A pyramid can also be denoted by 1 square. Here, the topmost and the lowermost square would be the same.

Input Format
The first line contains an integer, N, denoting the number of elements in S.
The next line contains an integer, K, denoting the number of elements in C.
Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing S[i].
Each line i of the K subsequent lines (where 0 ≤ i < K) contains an integer describing C[i].

Constraints
1 <= N <= 10^5
1 <= K <= 10^5
1 <= S[i] <= 10^5
1 <= C[i] <= 10^5

Sample Input Sample Output Explanation
Sample Input- 4

2
2
5
2
5
2
|Sample Output-|14|
|Explanation-N = 4, K = 2 Sizes = {2, 5, 2, 5} Count = {2, 2} In pyramid 1: Put squares like 2,5 (sum = 2 + 5 = 7) In pyramid 2: Put squares like 2,5 (sum = 2 + 5 = 7) Beauty of structure is 7 + 7 = 14|
Sample Input|4
2
7
1
1
12
3
1
Sample Output-|32|
Explanation-N = 4, K = 2 Sizes = {7, 1, 1, 12} Count = {3, 1} In pyramid 1: Put squares like 1,1,7 (sum = 1 + 7 = 8) In pyramid 2: Put squares like 12 (sum = 12 + 12 = 24) Beauty of structure is 8 + 24 = 32