Buying Candies

Problem code: BUYING

All Submissions

All submissions for this problem are available.

Emily is coming back from her two-week vacation at the other continent. But when Emily arrived at the airport, she realized that she had got no presents for her K friends! She still had some time before her flight, so she went for a walk around the airport hoping to find something suitable.

Soon Emily found a candy store and decided to buy some of her favorite candies for her friends. The store offers N packs of these candies, where pack i contains A_i candies.

Another reason Emily decided to buy candies is that she is fond of collecting empty candy packs from various parts of the world. That's why she decided to buy exactly M packs and present the friends with the candies and keep the packs for her collection. Emily would also like the total number of candies to be divisible by K so that an equal distribution of candies between friends is possible. Among all possible sets of packs, she would like to buy a set with the smallest possible total number of candies (money is the reason).

Your task is to help Emily, of course.

Input

The first line of the input file contains an integer T -- the number of test cases (no more than 5). T test cases follow, and each test case consists of two lines. The first of them contains three integers N, M and K (1 ? M ? N ? 50000, 1 ? K ? 20). The second of them contains N integers A_i (1 ? A_i ? 10⁹).

Output

For each test case, output just one line containing the smallest possible total number of bought candies, or -1 if it's impossible to buy exactly M packs so that the total number of candies is divisible by K.

Example

Input:
2
5 3 5
1 2 3 4 5
6 3 4
9 5 1 7 3 7

Output:
10
-1

Explanation:

In the first test case, it's impossible to buy one candy per friend as three smallest packs contain 6 candies all together. Two candies per friend is possible though -- for example, if you buy packs with 1, 4 and 5 candies.

In the second test case, buying 3 packs implies buying an odd number of candies, which is impossible to distribute equally among 4 friends.

Author:	gennady.korotkevich
Date Added:	12-11-2011
Time Limit:	3 sec
Source Limit:	50000 Bytes
Languages:	ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC

Submit

Comments

Login or Register to post a comment.

can she buy same pack more

dineshsingh @ 20 Nov 2011 09:39 PM

can she buy same pack more than once?

@dineshsingh No

anton_adm @ 20 Nov 2011 09:40 PM

@dineshsingh No

Im using Dev C++ 4.9.9.2

adu101992 @ 20 Nov 2011 10:57 PM

Im using Dev C++ 4.9.9.2 which option should I choose????

In this coing do I have to

adu101992 @ 20 Nov 2011 11:01 PM

In this coing do I have to represent the values as:- 2 535 12345 or can it be represented as:- Enter the number of test cases:2 Enter.................:5 ....................3 Enter.....................5 and so on

@adu101992: What do you mean

admin @ 20 Nov 2011 11:02 PM

@adu101992: What do you mean by option ?

@adu101992. n,m,k are written

anton_adm @ 20 Nov 2011 11:08 PM

@adu101992. n,m,k are written with only whitespace between n and m, and between m and k.

I meant should I choose C++

adu101992 @ 20 Nov 2011 11:09 PM

I meant should I choose C++ 4.3.2 or C++ 4.0.0.8 for submitting my code And Does the Input have to be one below the other as shown

oh k thnx :)

adu101992 @ 20 Nov 2011 11:09 PM

oh k thnx :)

@adu101992. You can choose

anton_adm @ 20 Nov 2011 11:10 PM

@adu101992. You can choose any version. Input will be one below the other.

Do I have to use the same

adu101992 @ 20 Nov 2011 11:11 PM

Do I have to use the same whitespace format in my coding too?

Thnx :)

adu101992 @ 20 Nov 2011 11:12 PM

Thnx :)

Should I end my program with

adu101992 @ 20 Nov 2011 11:38 PM

Should I end my program with a getch() so that the output can be seen. Is that why I get a wrong answer while submitting????????

No, you shouldn't.

anton_adm @ 20 Nov 2011 11:43 PM

No, you shouldn't.

K then Im confused why its

adu101992 @ 20 Nov 2011 11:47 PM

K then Im confused why its saying wrong answer when I submit my code???? Ill wait for this contest to finish to get to know about it thnx anyways

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a non-commercial competitive programming community

In order to report copyright violations of any kind, send in an email to copyright@codechef.com

CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month. We also aim to have training sessions and discussions related to algorithms, binary search, technicalities like array size and the likes. Apart from providing a platform for programming competitions, CodeChef also has various algorithm tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our programming contest judge accepts solutions in over 35+ programming languages. Preparing for coding contests were never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming challenges that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly coding contest and the shorter format Cook-off coding contest. Put yourself up for recognition and win great prizes. Our programming contests have prizes worth up to Rs.20,000 and $700lots more CodeChef goodies up for grabs.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be a part of CodeChef's Forums and interact with all our programmers - they love helping out other programmers and sharing their ideas. Have discussions around binary search, array size, branch-and-bound, Dijkstra's algorithm, Encryption algorithm and more by visiting the CodeChef Forums and Wiki section.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. You can also host a coding contest for your institute on CodeChef, organize an algorithm event and be a guest author on our blog.

Go For Gold

The Go for Gold Initiative was launched about a year after CodeChef was incepted, to help prepare Indian students for the ACM ICPC World Finals competition. In the run up to the ACM ICPC competition, the Go for Gold initiative uses CodeChef as a platform to train students for the ACM ICPC competition via multiple warm up contests. As an added incentive the Go for Gold initiative is also offering over Rs.8 lacs to the Indian team that beats the 29th position at the ACM ICPC world finals. Find out more about the Go for Gold and the ACM ICPC competition here.

Domain Name Registration, Web hosting, and Website Design provided by BigRock.com

Site Navigation