All Tracks Algorithms Sorting Problem

Christmas shopping
Tag(s):

Algorithms, Easy-Medium

Problem
Editorial
Analytics

x-mas tree

The Lalalandia's Christmas is coming! Only $$N$$ days are left and Jambo wants to buy all his friends a present. There are $$N$$ presents that his friends want and Jambo, because he is a very small elephant, cannot buy and carry more than $$K$$ presents at any day. Every present in $$j$$th day costs $$a_i * j$$ for every $$1 \le j \le N$$. Can you help Jambo determine the minimum amount of money needed to buy all presents and make his friends happy?

Input format

The first line consists of integers $$N$$ - the number of days and the number of presents Jambo wants to buy, and $$K$$ - the number of presents Jambo can carry. The second line contains n integers $$a_1, a_2, ..., a_N$$ — the cost of the $$i$$th present.

Output format

The first line should contain the single integer - answer to the problem.

Constraints:

$$1 \le N \le 10^5$$

$$1 \le K \le N$$

$$1 \le a_i \le 10^9$$

SAMPLE INPUT
3 1
1 2 3
SAMPLE OUTPUT
10
Explanation

Since $$K$$ equals to $$1$$, the optimal solution is $$3 * 1 + 2 * 2 + 1 * 3 = 10$$.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications