Limits 1s, 256 MB

Boba has opened a toy-manufacturing company that has nn workers, where exactly mm workers are newbies and the rest (nm)(n-m) workers are experienced. Each toy can be made by exactly one worker, but all workers can work in parallel on different toys. However, if an experienced worker takes tt time to complete one toy of a specific design, a newbie takes 2t2t to make the same toy (simply, twice as much time).

Boba's very good friend Kiki wants nn toys, each with different designs. Boba has done his calculations and prepared a dataset on how much time an experienced worker will need to complete each toy. Formally, he has prepared an array AA where the ii-th element aia_i denotes the amount of time an experienced worker will take to complete the ii-th toy.

Now, Boba has asked for your help to calculate the minimum amount of time required to complete all nn toys, if he assigns the workers to each toy optimally, also ensuring that every worker will work on at least one toy.

Input

The first line contains an integer nn (1n1000)(1 \le n \le 1000) denoting the number of toys Kiki wants.

The second line contains nn space-separated integers denoting the array AA, where the ii-th element aia_i (1ai109)(1 \le a_i \le 10^9) denotes the time an experienced worker will take to complete the ii-th toy.

The third line contains an integer mm (0mn)(0 \le m \le n) denoting the number of workers who are newbies.

Output

Print an integer in a single line denoting the minimum amount of time required to complete all toys in the given scenario.

Samples

InputOutput
3
5 11 8
1
11

The only newbie worker should work on the first toy.

InputOutput
3
7 13 7
2
14

The two newbie workers should work on the first toy and the third toy respectively.


Submit

Login to submit.

Statistics

96% Solution Ratio
SyedshakilmahmEarliest, 6M ago
nafim1703Fastest, 0.0s
Imran.666626Lightest, 5.1 MB
asifm91Shortest, 160B
Toph uses cookies. By continuing you agree to our Cookie Policy.