Speed Dial

Function

def assignNumbers (numbers, howMany, slots):

Problem Statement

Most telephones today are equipped with a speed dialing facility, which makes it possible to assign telephone numbers to single keys on your phone - although it's usually required to press some special speed dialing key first. However, there's usually a limit on how many numbers you can assign to the speed dial slots, so deciding which numbers you should assign can sometimes be tricky, if you want the optimal assignment.

Assume that you have made a list of all phone numbers you dial, and how many times you are dialing them each month. Now you want to find out which phone numbers you should assign to speed dialing slots in order to minimize the number of keys you have to press. For the purposes of this problem, you only have to return the total number of keypresses required if the optimal assignment is done.

In this problem, we assume that speed dialing a number takes exactly two keypresses, while dialing a number the default way requires exactly the same amount of keypresses as the length of the phone number. It's not possible to speed dial a number partially (for instance, speed dialing and then add two extra digits, or speed dialing twice to produce a single compound number).

Create a class SpeedDial containing the method assignNumbers which takes as parameters a list of numbers, numbers, containing the phone numbers, and a list of numbers, howMany, containing how many times you dial each number as well as a number, slots, the number of speed dialing slots your telephone has. An element in howMany is how many times you dialed the number in the corresponding element in the list numbers. The method should return the least number of keypresses required to dial all the numbers in a month.

Notes

There may be more speed dialing slots than actual phone numbers. In that case, some slots will be left unused (see example 1).

Since the numbers are given as an int, they cannot contain leading zeros.

Constraints

numbers will contain between 1 and 50 elements, inclusive.

numbers will contain the same number of elements as howMany.

howMany willcontain between 1 and 50 elements, inclusive.

Each element in numbers is between 1000 and 999999999, inclusive.

Each element in howMany is between 1 and 1000, inclusive.

The elements in numbers are unique.

slots is between 1 and 9, inclusive.

Examples


[9753,1245987,4833,34473,8733,1437 ]

[5,2,4,3,2,4]

4

Returns: 52

If we would dial all numbers without using speed dialing, the number of keypresses required would be 4*5 + 7*2 + 4*4 + 5*3 + 4*2 + 4*4 = 89.

The number of keypresses saved if we would assign each of the numbers to a speed dialing slot would be 10, 10, 8, 9, 4, and 8. So we should definitely assign 9753, 1245987 and 34473 to a speed dialing slot, and either 4833 or 1437. We would then save 10 + 10 + 9 + 8 = 37 keypresses, so the total number of keypresses required would be 89 - 37 = 52.


[124839,9876,43823]

[73,95,102]

5

Returns: 540

Here we have more slots than phone numbers, so all numbers in the list should be assigned to speed dialing slots. The total number of keypresses required would be 2*73 + 2*95 + 2*102 = 540.


[8925135,6046333,68260,29405,4830502,378742,13561,6090,976234,71994]

[5,35,2,34,33,14,43,42,29,10]

5

Returns: 695

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2002, TopCoder, Inc. All rights reserved.