SHELDON COOPER AND HIS BEVERAGE PARADIGM | Code vita 2015

Problem Description

Sheldon Cooper, Leonard Hofstadter and Penny decide to go for drinks at Cheese cake factory. Sheldon proposes to make a game out of this. Sheldon proposes as follows,

To decide the amount of beverage they plan to consume, say X.

Then order for a random number of different drinks, say {A, B, C, D, E, F} of quantities {a, b, c, d, e, f} respectively.

If quantity of any three drinks add up to X then we'll have it else we'll return the order. E.g. If a + d + f = X then True else False

You are given

Number of bottles N corresponding to different beverages and hence their sizes

Next N lines, contain a positive integer corresponding to the size of the beverage

Last line consists of an integer value, denoted by X above

Your task is to help find out if there can be any combination of three beverage sizes that can sum up to the quantity they intend to consume. If such a combination is possible print True else False

Input Format:

First line contains number of bottles ordered denoted by N

Next N lines, contains a positive integer Ai, the size of the ith bottle

Last line contains the quantity they intend to consume denoted by X in text above

Output Format: 

True, if combination is possible False, if combination is not possible

Constraints: 

N >= 3 Ai > 0 1 <= i <= N X > 0   

Example 1

Input:

6

1 4 45 6 10 8

22

Output:

True

Example 2

Input:

4

1 3 12 4

14

Output:

False

REVERSE GEAR | Code vita 2015

Problem Description

A futuristic company is building an autonomous car. The scientists at the company are training the car to perform Reverse parking. To park, the car needs to be able to move in backward as well as forward direction. The car is programmed to move backwards B meters and forwards again, say F meters, in a straight line. The car does this repeatedly until it is able to park or collides with other objects. The car covers 1 meter in T units of time. There is a wall after distance D from car's initial position in the backward direction.

The car is currently not without defects and hence often hits the wall. The scientists are devising a strategy to prevent this from happening. Your task is to help the scientists by providing them with exact information on amount of time available before the car hits the wall.

Input Format:

First line contains total number of test cases, denoted by N

Next N lines, contain a tuple containing 4 values delimited by space

F B T D, where

F denotes forward displacement in meters

B denotes backward displacement in meters

T denotes time taken to cover 1 meter

D denotes distance from Car's starting position and the wall in backward direction

Output Format:

For each test case print time taken by the Car to hit the wall

Constraints:

First move will always be in backward direction

1 <= N <= 100

backward displacement > forward displacement i.e. (B > F)

forward displacement (F) > 0

backward displacement (B) > 0

time (T) > 0

distance (D) > 0

All input values must be positive integers only

Example 1

Input:

2
6 9 3 18
3 7 5 20

Output:

162
220

SAVING FOR A RAINY DAY | Code vita 2015

Problem Description:

By nature, an average Indian believes in saving money. Some reports suggest that an average Indian manages to save approximately 30+% of his salary. Dhaniram is one such hard working fellow. With a view of future expenses, Dhaniram resolves to save a certain amount in order to meet his cash flow demands in the future. Consider the following example. Dhaniram wants to buy a TV. He needs to pay Rs 2000/- per month for 12 installments to own the TV. If let's say he gets 4% interest per annum on his savings bank account, then Dhaniram will need to deposit a certain amount in the bank today, such that he is able to withdraw Rs 2000/- per month for the next 12 months without requiring any additional deposits throughout. Your task is to find out how much Dhaniram should deposit today so that he gets assured cash flows for a fixed period in the future, given the rate of interest at which his money will grow during this period.

Input Format:

First line contains desired cash flow MSecond line contains period in months denoted by TThird line contains rate per annum R expressed in percentage at which deposited amount will grow

Output Format:

Print total amount of money to be deposited now rounded off to the nearest integer Constraints: M > 0 T > 0 R >= 0 Calculation should be done upto 11-digit precision 

Example 1

Input:

500

3

12

Output:

1470

Example 2

Input:

600

3

5.9

Output:

17824

Example 3

Input:

500

2

0

Output:

100

MILK MAN AND HIS BOTTLES | Code vita 2015

Problem Description

A Milkman serves milk in packaged bottles of varied sizes. The possible size of the bottles are {1, 5, 7 and 10} litres. He wants to supply desired quantity using as less bottles as possible irrespective of the size. Your objective is to help him find the minimum number of bottles required to supply the given demand of milk.

Input Format:

First line contains number of test cases N Next N lines, each contain a positive integer Liwhich corresponds to the demand of milk.

Output Format:

 For each input Li, print the minimum number of bottles required to fulfill the demand

Constraints:

1 <= N <= 1000 Li > 0 1 <= i <= N

Input

2

17

65

Output

2

7

Explanation:

Number of test cases is 2

For 17 = 10*1 + 7*1 = 2

For 65 = 10*6 + 5*1 = 7

Few more examples:

For 99 = 10*9 + 7*1 + 1*2 = 12

For 63 = 10*6 + 1*3 =9

SPORT STADIUM | Code vita 2018

It is the sports event of the year for the residents of Sportsville.  Their team had finally made it to the finals of the Bowls League Cup.

Problem Description

It is the sports event of the year for the residents of Sportsville.  Their team had finally made it to the finals of the Bowls League Cup.

They have booked tickets for the city contingent for the same row, and the size of the contingent (N) is smaller than the number of seats booked(S).Unfortunately, there was rain the previous night and some of the seats are still wet. Some of the contingent love Bowls so much and are excited enough not to mind sitting on a wet chair. There are k of these. However, others want to sit on a dry seat so that they can enjoy the match more.

The contingent wants to minimize the distance between the first and last person in the row so that they can still conduct Mexican Waves, and other forms of support for their team.

Because they want to sit together, any block of 15 or more contiguous unoccupied seats between the first person sitting and the last person sitting is unacceptable.

There are M blocks of seats, starting with a dry block, with alternating wet and dry blocks.  The number of seats in each block is known.

Given S (the number of seats in the row), N (the size of the contingent),k (the number of the contingent who are willing to sit in a wet seat), and the distribution of wet and dry blocks, write a program to find the minimum distance between the first and the last member of the contingent in the row.

Input

The first line contains four comma separated numbers representing S, N, k and M respectively.

The second line is a set of M comma separated numbers representing the number of seats in each block of seats.  The first block is dry, and the remaining blocks alternate between wet and dry.

Output

One integer representing the minimum distance between the first and last member of the row.  If it is impossible to seat all the members according to their preferences,and with the unoccupied seat restriction,  the result should be 0.

Constraints

S,N,k < 1000,  M < 30

Example 1

Input

100,50,5,6

3,10,30,5,30,22

Output

49

Explanation

S = 100, and there are 100 seats in the row.  N=50, and there are 50 members in the contingent. k=5, and 5 people (out of the 50) do not mind sitting on wet seats.  M=6, and there are 6 blocks of seats.  The number of seats in each block is 3,10,30,5,30 and 22, with the first block of 3 seats being dry, the next 10 being wet and so on.

One possible positioning to achieve the minimum distance is to place the a set of 30 people in seats 14 to 43 (the dry block), the 5 people who do not mind sitting on wet seats in the wet block 44 to 48, and the remaining 15 people (of the 50) in the seats 49 to 63.  There is no unoccupied seat between the first person and the last person, and so this is acceptable.The distance between the last allocated seat (63) and the first allocated seat (14), is 49.  This is the output.

Example 2

Input

100,50,5,8

3,7,10,10,20,10,20,20

Output

64

Explanation

S = 100, and there are 100 seats in the row.  N=50, and there are 50 members in the contingent. k=5, and 5 people (out of the 50) do not mind sitting on wet seats.  M=8, and there are 8 blocks of seats.

One possible positioning is to have a set of 10 people sit in the dry block 11 – 20, the 5 people who will accept wet seats in seats 21 – 25 (in the wet block 21 – 30), another 20 people in the dry block 31 – 50, leave the wet block 51-60 empty, and seat the remaining 15 people in seats 61 – 75 (in the dry block 61-80.  There is a block of 5 unoccupied seats (26-30) between the first person and the last person.  As this is not more than 15, this is acceptable. The distance from the last allocated seat (75) and the first allocated seat (11) is 64.  This is the result.

OBSTACLE GAME | Code vita 2018

Given a n*n Array matrix (A) with A[0][0] element as the starting point and any one element as the destination.

Problem Description

Given a n*n Array matrix (A) with A[0][0] element as the starting point and any one element as the destination. Find the destination and print the route map.

Rules:

1. Array Matrix with n*n elements such that n >=2 and n<=10.

2. Starting point A[0][0] value will be 'A'.

3. Destination value will be 'D'

4. There will be always 1 continuous route which can be straight or diagonal.

5. There are 4 types of hurdles and corresponding values :

a. Stone denoted by 'S'

b. Wall denoted by 'L'

c. Water denoted by 'W'

d. Thorn denoted by 'T'

6. Music provides mind peace. Which will be denoted by 'M'. It is not a hurdle.

6. The value of route will be 'R'.

Input

First Line contains dimension N of Matrix A.

Next N Lines, each contains N values delimited by space

Output

At every Step print the surrounded hurdles in ascending order of values. i.e. for every 'R' print the surrounding hurdles.

If there are no hurdled around step in the route, print 'NO HURDLES' for that step.

On reaching destination print 'DESTINATION'

Music 'M' is not a hurdle. It should not be included in output.

Constraints

2 <= N <= 20

Example 1

Input

4

A S L D

T R W R

R M S R

W R R M

  

Output:

L S S T W

T W

S W

S

S W

L S W

DESTINATION

Example 2

Input:

5

A S L W M

R S L D T

M R T R M

T L R M S

S L S W T

Output:

S S

L L S T T

L L S T W

L S T T

DESTINATION

INCREASING SUBSEQUENCE WITH LARGEST SUM | Code vita 2017

Problem Description:

Given a sequence a1, a2, ..... an, of positive integers, a strictly increasing subsequence is a subsequence of the given sequence such that each term of the subsequence is strictly less than the next. For example, in the sequence 1, 2, 10, 3, 7 , 4, two strictly increasing sub sequences are 1, 10 and 2, 3, 4

The Input consists of N sets of five integers each. From these sets, a derived sequence is formed by selecting one of the five numbers in each set as part of the sequence.   

The objective is to pick the numbers from each set so that the corresponding derived sequence has the strictly increasing subsequence with the largest sum. 

Input 

The first line of the input has a positive integer N which is the number of sets of the numbers in the input. Each of the next N lines consists of a set of five (not necessarily distinct) comma separated positive integers. 

Output 

The sum of the elements of the longest strictly increasing subsequence in all possible derived sequences 

Constraints   

N<=50 
Integers in sets<=10000

Example 1    

Input:  

5 
3000,400,1500,4350,2700 
2050,3650,650,2750,4300 
2000,700,2100,700,1650 
300,200,500,600,200 
3000,3100,3200,1100,1400 

Output: 

8850 

Explanation: 

A possible derived sequence from the input which gives the maximum sum for a strictly increasing subsequence is 1500,2050,2100,500,3200 (one from each row), and the strictly increasing subsequence that gives the maximum sum from this from this is 1500,2050,2100,3200, whose sum is 8850, which is the output

Example 2    

Input:  

6
800,3000,600,3600,800 
1400,5200,1600,6000,2600
3200,3800,3200,1600,2400
800,2800,4800,600,1400
5200,1400,4800,3800,800
5000,4200,4800,1800,2000 

Output:  

17400 

Explanation:  

A possible derived sequence that gives a maximum sum for a strictly increasing subsequence is 800, 1600, 2400, 2800, 4800, 5000. All appear in the strictly increasing subsequence, and the sum is 17400, which is the output

SKYLINE | Code vita 2017

Problem Description:

Humans have now set up housing societies on the moon, where the societies are very large, and each building can be very high. There are N consecutive buildings in a society. The owners decided to increase the heights of the buildings. Being aesthetically oriented, they wanted to ensure that the heights (all measured as number of floors in the building) of consecutive buildings differ at most by one floor so that the skyline of the buildings look pleasing. That is, if the heights of the buildings are h1, h2, ... hn, then after the height increase, their heights become H1, H2, .... Hn such that ­1 <= Hi ­ H(i+1) <= 1 for all i = 1, 2, ...n­1. The modification is made such that the total number of floors added to the society is a minimum.

The owner of the pth building wants to know what will be the height of his building before agreeing to this plan for modification, Given the initial heights of the buildings, can you write a program to answer the query pth owner has?  

Input    

T number of test cases   

A set of 2 lines for each of the T test cases containing   

N, the number of buildings, P the position the building for which we want to know the height after modification   

N space separated integers showing the original heights of the buildings 

Output    

T lines containing   

height of the Pth building after modification for each of the T test cases   

Constraints   

1<=T<=50   

1<=N<=104 P<=N   

1<=height of each building <= 5000 (There are very tall buildings in the society) 

Example 1  

Input:  

1  

7 4  

9 5 17 7 10 2 18   

Output:  

16   

Explanation:  

After modification the heights will become 15 16 17 16 16 17 18. Hence the fourth building will have height 16 floors.   

Example 2    

Input:  

1  

13 12  

34 80 56 41 16 39 70 85 73 75 20 33 83   

Output:  

82   

Explanation:  

After modification, the heights would be  79 80 80 81 82 83 84 85 84 83 82 82 83

ON A CUBE | Code vita 2017

Problem Description:

A solid cube of 10 cm x 10cm x 10 cm rests on the ground. It has a beetle on it, and some sweet honey spots at various locations on the surface of the cube.  The beetle starts at a point on the surface of the cube, and goes to the honey spots in order along the surface of the cube.

1. If it goes from a point to another point on the same face (say X to Y), it goes in an arc of a circle that subtends an angle of 60 degrees at the centre of the circle

2. If it goes from one point to another on a different face, it goes by the shortest path on the surface of the cube, except that it never travels along the bottom of the cube

The beetle is a student of Cartesian geometry, and knows the coordinates (x, y, z) of all the points it needs to go to. The origin of coordinates it uses is one corner of the cube on the ground, and the z axis points up. Hence, the bottom surface (on which it does not crawl) is z=0, and the top surface is z=10. The beetle keeps track of all the distances travelled, and rounds the distance travelled to two decimal places once it reaches the next spot, so that the final distance is a sum of the rounded distances from spot to spot.

Input Format:

The first line gives an integer N, the total number of points (including the starting point) the beetle visits

The second line is a set of 3N comma separated non-negative numbers, with up to two decimal places each. These are to be interpreted in groups of three as the x, y, z coordinates of the points the beetle needs to visit in the given order

Output Format:

One line with a number giving the total distance travelled by the beetle accurate to two decimal places. Even if the distance travelled is an integer, the output should have two decimal places.

Constraints:

None of the points the beetle visits is on the bottom face (z=0) or on any of the edges of the cube (the lines where two faces meet)

2≤N≤10

Example 1

Input

3

1,1,10,2,1,10,0,1,9

Output

4.05

Explanation

There are three points visited by the beetle (N=3). The beetle starts on the top face of the cube (z=10) at point (1,1,10) and goes to another point on the same face (2,1,10). Though the straight line distance is 1, it travels on the arc of a circle subtending an angle of 60 degrees at the centre of the circle, and hence travels (2*π)/6 or 1.05 (note that it rounds the distance at each leg of the journey). It then travels from (2,1,10) on the face z=10 to (0,1,9) on the face x=0 along the surface of the cube. This is a distance of 3. The total distance travelled is 1.05+3=4.05. The output is 4.05

Example 2

Input

3

1,1,10,2,1,10,0,5,9

Output

6.05

Explanation

There are three points visited by the beetle (N=3). The beetle starts on the top face of the cube (z=10) at point (1,1,10) and goes to another point on the same face (2,1,10). As before. This distance is 1.05. It then travels from (2,1,10) on the face z=10 to (0,5,9) on the face x=0 along the surface of the cube. The shortest distance on the surface of the cube between these points is 5. The total distance travelled is 1.05+5=6.05. The output is 6.05

CONTINUOUS NIVEN NUMBERS | Code vita 2017

Problem Description:

In recreational mathematics, a Niven number in a given number base, is an integer that is divisible by the sum of its digits when written in that base. For example, in base 10, 18 is a Niven number since 18 is divisible by 1+8 = 9. Also, 12001 in base 3 is also a Niven number since the sum of the digits is 4 (which is 11 in base 3) divides 12001 (12001 = 1021 x 11).

Given a base b, any number n < b is trivially a Niven number. We will ignore this case.

Given a base b, and a positive integer T, find the lowest number L such that L, L+1, ..., L+T-1 are all Niven numbers but neither L-1 nor L+T are Niven numbers.

Input Format:         

First line contains two integers, b and T

Output Format:

A single integer L such that L, L+1, ..., L+T-1 are all Niven numbers but neither L-1 nor L+T are Niven numbers.

Constraints:

2 ≤ b ≤ 10

1 < T < 7

Example 1

Input

10 4

Output

510

Explanation

510, 511, 512 and 513 are Niven numbers and 514 is not a Niven number. Also 509 is not a Niven number. It can be seen that for N < 510, no four consecutive numbers are Niven numbers.

Example 2

Input

5 5

Output

44

Explanation

44 in base 5 is equivalent to 24 in base 10. Clearly, sum of the digits is 8 = 13 in base 5 and 13 x 3 = 44 in base 5 and hence 44 is a Niven number. Similarly we can see 44+1 = 100, 101, 102 and 103 in base 5 are also Niven numbers. 104 is not a Niven number.

COUNTING NUMERIC SUBSEQUENCES | Code vita 2017

Problem Description:

If one is given a string of length N, there are two ways of specifying substrings of it. One way is to give the string representation, namely the substring itself. The other way is to specify a numeric subsequence of the numbers (1,2,3,... N). These correspond to the positions in the original string of the characters of the substring.

Thus if the string "tcsin", the numeric subsequence (1,3,5) represents the substring whose characters are from the positions 1,3,5 from the original string, or the substring "tsn".

Regular expressions are a very standard way to represent patterns in strings. One symbol in it is "+", which represents all strings that have one or more occurrences of the preceding character. Thus the regular expression t+c+s+i+n+ represents any string which has a string of t's followed by a string of c's followed by a string of s's followed by a string of i's followed by a string of n's. Each of these strings of repeating letters must have at leat one character. Thus ttcsssiiiiinn, tcsin, tcccsiin all satisfy it, while tcin does not (the string of s's has 0 characters) and tscin does not (the string of c's is after the string of c's, when it should be before).

If the length of the string is N, the objective is to count the number of distinct numeric subsequences of (1,2,3,... N) that correspond to a substring that matches the regular expression t+c+s+i+n+

Input

The input will be one line of a string of letters.

Output

The output is the remainder when the number of distinct numeric subsequences is divided by (109+7)

Constraints

5≤ N ≤ 105

Example 1

 

Input:

tcstcsin

Output:

7

Explanation:

Here, N is 8, and we are looking for distinct subsequences of (1,2,...8). The distinct numeric subsequences and the corresponding substrings are given. It may be seen that all the substrings match the regular expression, and there are no more numeric subsequences that correspond to substrings that match the regular expression. As there are 7 distinct numeric subsequences, the output is 7. [the remainder when 7 is divided by (109+7)]

Numeric        Substring

(1,2,3,7,8)               tcsin

(1,2,3,6,7,8)            tcssin

(1,2,6,7,8)               tcsin

(1,2,5,6,7,8)            tccsin

(1,5,6,7,8)               tcsin

(1,4,5,6,7)               ttcsin

(4,5,6,7)                  tcsin

Example 2

Input:

tcsintcsin

Output:

11

Explanation:

Here, N is 10, and we are looking for distinct subsequences of (1,2,...10). The distinct numeric subsequences and the corresponding substrings are given. It may be seen that all the substrings match the regular expression, and there are no more numeric subsequences that correspond to substrings that match the regular expression. As there are 11 distinct numeric subsequences, the output is 11 [the remainder when 11 is divided by (109+7)]

Numeric                    Substring

(1,2,3,4,10)                tcsin

(1,2,3,4,5,10)             tcsinn

(1,2,3,4,9,10)             tcsiin

(1,2,3,4,10)                tcsin

(1,2,3,8,9,10)             tcssin

(1,2,8,9,10)                tcsin

(1,2,8,9,10)                tcsin

(1,2,7,8,9,10)             tccsin

(1,7,8,9,10)                tcsin

(1,6,7,8,9,10)             ttcsin

(6,7,8,9,10)                tcsin

(1,2,3,4,5)                  tcsin

ROUND VAULTS IN BANK | Code vita 2017

Problem Description:

In the strong room of ABC bank there are N vaults arranged in a circle. The amount of money inside each vault displayed on the door. You can empty any number of vaults as long as you do not empty more than 2 out of any 5 adjacent vaults. If you attempt to break more than 2 of any 5 adjacent vaults, an alarm sounds and the sentry a sharp shooter will kill you instantly with his laser gun! Note that as the vaults are arranged in a circle, the last vault is adjacent to the first one.

The output is the maximum amount of money that can be emptied without sounding the alarm

Input Format:

The first line contains an integer N which is the number of vaults. The next line has a sequence of positive integers of length N, giving the amount of cash in its vaults in order

Output Format:

The maximum amount of money that can be looted without sounding the alarm.

Constraints:

N<=50, Amount in each vault <=50000

Example 1

Input

9

1000, 2000, 1000, 5000, 9000, 5000, 3000, 4000, 1000

Output

15000

Explanation

The vaults 1, 5, 6 are looted, giving a total loot of (1000+5000+9000)=15000

Example 2

Input

10

1000,2000,3000,5000,9000,7000,6000,4000,7000,5000

Output

26000

Explanation

There are 10 vaults arranged in a circle. The amounts in the vaults are 1000, 2000, ... 5000.

One way of getting the maximum is to loot vaults 4, 5, 9 and 10 giving a total of 26000. Hence the output is 26000. Note that no 5 adjacent vaults have more than 2 looted.

PALINDROME SORTING | Code vita 2017

Problem Description:

A palindrome is a word, phrase, or sequence that reads the same backwards as forwards. Given a palindrome write a program to print the sorted list of all palindromes that can be constructed from the alphabets of the given palindrome. All palindromes should start in a newline.

Input Format:

The first line, an integer T, indicating the number of test cases
T lines each containing one string (palindrome)

Output Format:

For each test case, one line indicating the Test case number
The next lines containing a sorted list of all palindromes constructed from the given palindrome of the ith test case

Constraints:

T ≤ 10

Example 1

Input 

1
NITIN

Output 

INTNI
NITIN

Explanation 

There are only two palindromes that can be constructed from NITIN

Example 2

Input 

1
ABCDCBA

Output 

ABCDCBA
ACBDBCA
BACDCAB
BCADACB
CABDBAC
CBADABC

Explanation 
Since there is only one D, it can only be the middle letter in the palindrome. The remaining lettere A, B, C can be arranged in 6 possible ways and each way gives rise to a palindrome.

CONCATENATING PRIME | Code vita 2017

Problem Description:

If you like numbers, you may have been fascinated by prime numbers. Sometimes we obtain by concatenating two primes. For example, concatenating 2 and 3, we obtain the prime 23. The aim is to find all such distinct "concatenated primes" that could be obtained by concatenating primes ≤ a given integer N.

Input Format:

Integer N

Output Format: 

M, the number of distinct primes that could be obtained by concatenating two primes ≤ N

Constraints:

N ≤ 70

Example 1 

Input

10

Output

4 

Explanations

The primes ≤ 10 are 2, 3, 5, 7. These can be used to form the following concatenated numbers: 22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75, 77. Of these, there are four primes: 23 37 53 and 73. Hence the output is 4. 

Example 2

Input

20 

Output

17 

Explanation

The prime numbers up to 20 are 2 3 5 7 11 13 17 and 19. 

Concatenating these two at a time in all possible ways, we get the following numbers:

22 23 25 27 211 213 217 219

32 33 35 37 311 313 317 319

52 53 55 57 511 513 517 519

72 73 75 77 711 713 717 719

112 113 115 117 1111 1113 1117 1119

132 133 135 137 1311 1313 1317 1319

172 173 175 177 1711 1713 1717 1719

192 193 195 197 1911 1913 1917 1919

We have the following 17 primes numbers in this list: 23 37 53 73 113 137 173 193 197 211 311 313 317 719 1117 1319 1913 Hence the output would be 17.

BOOK FAIR | Code vita 2017

Problem Description:

It is the Annual Book Fair. There are thousands of book stalls and this year the organizers introduced a new scheme. In every stall either you can collect a coupon bearing a number but then you must skip next k stalls or you can simply go to the next stall without collecting the coupon. At the end, your prize is free books worth the sum of the numbers on the coupon you have collected.

Input Format:

The first line has two positive integers, N (the number of stalls) and k (the number of stalls to skip if you collect a coupon).

The next N lines have 1 positive integer each, which is the value of the coupons you collect from the corresponding stall.

Output Format:

The output is one number that is the maximum value of the sum of coupons collected according to the rules.

Constraints:

N<50

Number on the coupon <1000

Example 1

Input

10,2

4

5

8

7

5

4

3

4

6

5

Output

19

Explanation

N =10, k=2

The highest value is obtained if you pick the stall numbers 1,4,7,10, giving a value of 4+7+3+5=19.

Example 2

Input

10,2

50

70

40

50

90

70

60

40

70

50

Output

230

Explanation

There are 10 stalls, and k=2. The coupon values are as shown. If you visit stalls 2, 5 and 9, you get a total value of 230, which is the maximum possible. The output is 230.