407776: GYM102892 5 Channel Surfing

You want to buy a TV, and you're looking into your options. You're going to base this decision on the daily TV schedule for $$$n$$$ channels. The schedule lists the first $$$m$$$ minutes in the day. Each of the $$$n$$$ channels has interesting content for some of the minutes during the day, and uninteresting content for all of the other times during the day.

The TVs offered all have a certain amount of channels that they are able to record content from at one time, which is what you're using to try to decide which TV to buy.

You have a value called your TV score which starts at 0, and increases as you record content.

Each of the $$$n$$$ channels has a certain enjoyment value, which is a positive integer. For each minute that you record a TV channel, if the channel has interesting content, your TV score will increase by the channel's enjoyment value, and if the channel has uninteresting content, it won't change.

In each minute of the day, you can choose to record as many channels as your TV allows. You can freely switch between recording different channels between each minute, but not during minutes.

Your task is to find the minimum number of channels that your TV needs to be able to record at once, in order to attain a TV score of at least $$$k$$$.

The first line of input contains three space-separated integers $$$n$$$ $$$(1 <= n <= 1000)$$$, $$$m$$$ $$$(1 <= m <= 1000)$$$, and $$$k$$$ $$$(1 <= k <= 10^{18})$$$: the number of TV channels, the number of minutes that the schedule covers, and your goal value for the TV score, respectively.

The next line contains $$$n$$$ space-separated integers: the enjoyment value for each TV channel. Each enjoyment value will be between $$$1$$$ and $$$10^9$$$, inclusive.

The next $$$n$$$ lines each consist of a $$$m$$$-character string of ones and zeros, with each 1 character representing interesting content at the corresponding minute, and each 0 character representing uninteresting content.

Output a single positive integer $$$c$$$: the minimum number of channels that your TV needs to be able to record during a single minute, in order to be able to attain a TV score of at least $$$k$$$.

If it is impossible to attain a TV score of at least $$$k$$$ across all channels, output $$$-1$$$.

Full problem: 24 points

4 15 133
5 9 3 11
000111011000000
111111010001111
101100011011000
000110000001000

2

3 5 729
11 13 14
11000
01000
00111

-1

In the first example, if you buy a TV that can record only 1 channel at once, you can attain a TV score of 113, which is not enough. If you buy a TV that can record 2 channels at once, you can get a TV score of 159, so this is the answer.

In the second example, even if you buy a TV that can record all three channels, you only get a TV score of 77, which is not enough.