SQRMINSUM - Minimum Sum

Suppose you have a list of integers, and a move is defined as taking one of the integers from the list and replacing it with its square root, rounded down to the nearest integer.

Given an integer l and an integer k, start with the array [1, 2, 3 ... l] and find the minimal sum of the array after k moves.

Example

For l = 5 and k = 2, the output should be squareRoots(l, k) = 10.

We start with [1, 2, 3, 4, 5].

After square rooting 5 to get [1, 2, 3, 4, 2] and then square rooting 3 to get[1, 2, 1, 4, 2], we end up with a sum of 10.

Constraints

1 ≤ l ≤ 104

1 ≤ k ≤ 104

T=10000

Input

The first line contains T the number of test cases followed by 2*T lines containing l and k.

Output

For every test case, output one line containing an integer, i.e. the minimal possible sum.

Sample

Input:
2
5
2
2327
4895

Output:
10
10647

Added by:Piyush Kumar
Date:2016-06-10
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Standard Pro Co

hide comments
2021-08-04 15:06:08
rounded down to the nearest integer means that the square root for 7 is 2, not 3. (floor not round) costed me a lot of WA
2020-01-03 08:03:41
Good question . Hint - No need of priority queue . just start thinking
2018-04-19 07:22:18 Ishan
O((k+l)*log(l)) with C++ STL's priority queue is sufficient, just be careful not to use computation heavy floating point calculating like sqrt() etc.
2017-11-17 08:10:50
Good time limit so you get to see what you're doing right. Turns out you can even pass with pure Python! Coding style makes all the difference. Great problem.
2017-03-22 14:04:03 saurabh
can anyone help me what to use instead of priority queue to avoid TLE
2017-03-07 09:59:06
easy one no need of priority queue ....
2016-07-12 08:49:07
It does indeed give the feel of a @vectar31 type problem ;)

BTW, no queue nothing needed!

Last edit: 2016-07-12 08:49:43
2016-06-30 15:27:31
@vectar31 Bro you're an inspiration to me. Can you please give me Your History of submission" (Plaintext Version)"..So that i Could follow it!!!

Re: I am just average :) ! Ask Francky, numerix, min_25, Tjandra, Mitch :) !

Last edit: 2016-06-30 17:41:29
2016-06-30 08:19:11
why priority queue in pypy gives TLE?
Edit: Thanks Did it in too slow pypy..hehe
Re: Because there are better ways to solve this problem. PyPy is too slow to beat the TL, faster languages might just manage to do that, but that is not what this problem expects you to do.

Last edit: 2016-06-30 10:37:30
2016-06-25 10:14:14 Shubhransh Srivastav
fast i/o+priority queue...just managed to beat the time limit :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.