Maximize total bandwidth of data channel pairs

You are optimizing how information flows through a network of processing nodes.

There are n processing nodes. The bandwidth capability of the i-th node is given by an integer array bandwidth of length n.

There are streamCount data channels that must each be connected to two processing nodes:

• one node acts as the main connection;
• the other acts as the secondary connection.

For a single data channel with main node index i and secondary node index j, its data flow is defined as:

dataFlow = bandwidth[i] + bandwidth[j]

A pair of nodes (i, j) used for one channel must be unique among all channels, with the following rules:

• A pair is identified by the ordered indices (main, secondary).
• (i, j) and (j, i) are considered different pairs.
• It is allowed to choose i == j, i.e., a channel may use the same node for both main and secondary.
• The same node index can appear in many different pairs (across different channels), as long as the ordered pair (i, j) itself is unique for each channel.

Your goal is to select exactly streamCount distinct ordered pairs (main, secondary) so that the sum of dataFlow across all data channels is maximized.

Input

• An integer n (number of nodes).
• An integer array bandwidth of length n, where bandwidth[i] is the bandwidth of node i.
• An integer streamCount — the number of data channels.

You may assume:

• 1 <= n <= 10^5.
• 1 <= bandwidth[i] <= 10^9.
• 1 <= streamCount <= n^2 (since there are n^2 possible ordered pairs (i, j) including i == j).

Output

• Return a single integer: the maximum possible total dataFlow, i.e., the maximum possible sum of bandwidth[main] + bandwidth[secondary] over all streamCount channels.

Complexity requirement

Design an algorithm that works efficiently for n and streamCount up to about 10^5 (much better than enumerating all n^2 pairs explicitly when n is large).