Need help in Question - of course not a stupid one

we have been given N which represents that there are N no. of sticks available with li length and frequency Ai. We have two choices, either we can make a square or a rectangle using these sticks. Ofcourse we can use a single unit of stick once only.
Let S be the sum of lengths of sticks that are used to make square and rectangles. We have to maximize the value of S.
Of course, you can make as many squares and rectangle as you want (of course they should be valid).

Given Testcase :
4
5 6
3 2
4 3
6 1

ans —> 38

Let me explain to you my approach what I was trying but I am not sure this is correct or not that’s why I am asking for help:
what I was doing is Let’s make as many as squares we can make. Now put all the left values in a max heap and every time pop() two maximum values and make rectangles out of them.

But one of my thought is saying that this problem looks like knapsack where we have to choose certain quantities from a given set.
Kindly help

2 Likes