# Amazon Online Assessment 2021 (OA) - Maximum Quality

Amazon's AWS provides fast and efficient server solutions. The developers want to stress-test the quality of the servers' channels. They must ensure the following:

• Each of the packets must be sent via a single channel.
• Each of the channels must transfer at least one packet.

The `quality` of the transfer for a channel is defined by the median of the sizes of all the data packets sent through that channel.

Note: The median of an array is the middle element if the array is sorted in non-decreasing order. If the number of elements in the array is even, the median is the average of the two middle elements.

Find the maximum possible sum of the qualities of all channels. If the answer is a floating-point value, round it to the next higher integer.

### Input

• `packets`: the packet sizes
• `channels`: the number of channels

### Output

the maximum sum possible

### Examples

#### Example 1:

Input:

``````1discounts = [1, 2, 3, 4, 5]
2channels = 2``````

Output: `8`

Explanation:

One solution is to send packet {5} through one channel and {1, 2, 3, 4} through the other. The sum of quality is 5 + (2 + 3)/2 = 8.

#### Example 2:

Input:

``````1discounts = [2, 2, 1, 5, 3]
2channels = 2``````

Output: `7`

Explanation:

One solution is to send packet {5} through one channel and {2, 2, 1, 3} through the other. The sum of quality is 5 + (2 + 2)/2 = 7.

### Constraints

• `1 <= len(packets) <= 5 * 10^5`
• `1 <= packets[i] <= 10^9`
• `1 <= channels <= len(packets)`

## Title

### Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. `Lorem` `Ipsum` has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, `Lorem` `Ipsum` is not simply random text.

``````1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3``````