## CEOI '16 P5 - Popeala

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

The Romanian word "popeală" has its origins in a Romanian historical novella, "Alexandru Lăpușneanul", where the eponymous Prince of Moldavia uses a variation of the term to describe his upcoming revenge on his usurpers. The term was recently revived, somewhat surprisingly, in the Romanian programming contest scene. It's used to describe any situation in which the scientific committee makes life harder for the contestants in an unorthodox and (usually) involuntary way: very strict time limits, invalid test cases, wrong statements, stealing keyboards and other such mechanisms. This task is about such a "popeală".

Consider a programming contest with contestants. The contest has only one task which has test cases. The scientific committee wants to group these test cases into at most subtasks.

How subtasks work: Each test case will belong to exactly one subtask. A subtask can contain any number of test cases, but it cannot be empty. If a contestant fails any test case of a certain subtask, his or her score for that subtask will be . Otherwise, the score for that subtask will be equal to the sum of score values of all of its test cases.

This is a common practice in programming contests, but the catch is that the scientific committee wants to do this after the contest is over. They know what test cases were solved correctly for each contestant and they want to group the tests into subtasks such as to minimize the total number of points scored in the contest.

Specifically, you are given an integer array Points[] of size . Points[i] will contain the point value of the -th test. You are also given a two-dimensional array Results[][] of size . Results[i][j] will be equal to if the -th contestant has correctly solved the -th test case.

Otherwise, it will be equal to . The committee has already decided that all subtasks will contain consecutive test cases. In other words, if test cases and will end up in the same subtask, then every test case , with must also belong to this subtask.

You should help the committee. They want to know, for each value , what is the minimum total number of points that can be earned in the contest if they choose to group the test cases into exactly subtasks.

#### Input

The input will contain three space-separated positive integers on its first line: . The second line will contain space-separated positive integers, representing the elements of the Points[] array. The following lines will each contain a binary string of length , representing the elements of the Results[][] matrix.

#### Output

The output should contain lines. The -th line should contain a single integer: the minimum total number of points that can be earned in the contest if the test cases are grouped into subtasks.

#### Notes and constraints

• Points[i] , for all . It is also guaranteed that Points[1] Points[2] Points[T] for all test cases.
• For test cases worth points, .
• For test cases worth another points, .
• For test cases worth another points, .

#### Sample Input

2 3 3
4 3 5
101
110

#### Sample Output

0
8
16

#### Explanation for Sample Output

There are contestants, test cases and , which means we must compute the minimal score for and subtasks, respectively. The Points[] array is .

In the case of a single subtask, the total number of points that can be achieved is equal to , because neither contestant has solved all cases correctly, and all test cases must be in the same subtask.

There are two ways to group the test cases in two subtasks. One of them produces a total number of points and the other one a total of points. Because we are looking to minimize this value, we choose the latter.

There is also a single way to group the test cases into three subtasks, which produces a total number of points.