oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

spacetravel Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

spacetravel.html

Problem Description

You are still an inter-galactic traveller in a 1-dimensional space. Sadly, there are no wormholes to help you now. However, on your last trip, you have acquired s number of dark matter spheres.

These dark matter spheres are special objects, they allow you to travel twice as fast. This indicates that the time required for any trip will be halved.

Possessing such dark matter spheres, you want to minimize the time of your future trips so that you spend the least amount of time travelling in space.

Each future trip is actually a round-trip, meaning that for the ith trip, you take ti years to reach your destination, and then ti years to return. Using a sphere will increase your speed for the entire trip, making the duration required much shorter.

You can only use one sphere of dark matter for each trip.

Input

The first line of input consists of 2 integers, n and s. n is the number of future trips you are going to engage in. s is the number of dark matter spheres you possess.

The following lines of input will consist of n space-separated numbers, with the ith number being ti.

n and s will be not more than 1000 and the amount of time required for each trip will be not more than 1000 as well.

Output

Output the shortest amount of time you need to travel in space yet still accomplishing all the trips, in years.

Sample Input

5 3
5 8 9 1 3

Sample Output

30

Explanation for Output

Without using any spheres, the total time required will be 5*2 + 8*2 + 9*2 + 1*2 + 3*2 = 52

Using 3 spheres, the lowest amount of time required will be 2.5*2 + 4*2 + 4.5*2 + 1*2 + 3*2 = 30

Tags

Sorting

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100101s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o spacetravel -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.