As the sole employee in a pharmaceutical company with programming exposure, you have been asked to oversee the process of cutting DNA strands into smaller pieces, which has been outsourced to a company by the name of Chopper!, and check for any attempt of over charging.
DNA (Deoxyribonucleic acid) strand is a long polymer of simple units called nucleotides, with a backbone made of sugars and phosphate atoms joined by ester bonds. Attached to each sugar is one of four types of molecules called bases. It is the sequence of these four bases along the backbone that encodes information needed to construct other components such as proteins and RNA molecules. The cost of cutting a DNA strand, with today's technology, is equal to the length of the strand, where a ``cut" refers to splitting a strand into two pieces. The cost of a single cut does not depend on the location where the cut is made. Chopper! claims to have developed the world-best-practice in sequencing the cuts of a DNA strand and to deliver the most savings to its customers.
Your task is to write a program to process the next batch of DNA strands and calculate the best price for slicing each of them into smaller strands of integer lengths. For each DNA strand you are given its length as an integer N , N ≤ 10000 , and a list of M , 2 ≤ M ≤ 15 , strands' lengths to be produced. The sum of the M integers equals the original strand length N .
The total cost of slicing a given strand depends on the choice of locations and the order of the M - 1 required cuts. As an example, for a given list of M (=4) lengths 2, 2, 5 and 5 and a DNA strand of length 14, we can:
The input contains information about a number of DNA strands to be processed. The information for each strand consists of two lines:
The input is terminated by a line of two zeros (0 0) for which no output is to be produced.
For each input DNA strand the output is an integer, on a separate line, which represents the minimum cost for slicing the strand into the given list.