407776: GYM102892 5 Channel Surfing

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

5. Channel Surfingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$$$.

Input

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

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$$$.

Scoring

Full problem: 24 points

ExamplesInput
4 15 133
5 9 3 11
000111011000000
111111010001111
101100011011000
000110000001000
Output
2
Input
3 5 729
11 13 14
11000
01000
00111
Output
-1
Note

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.

加入题单

上一题 下一题 算法标签: