Greedy Midgets Game

    Our dwarf is very nice, but he is a little greedy. He and his friend heard about a valley that they
can collect lots of coins. Unfortunately they can also lose some of the coins.

    The two dwarfs have a set of maps which show a correct pattern of steps through the valley. Since
they are greedy dwarfs, they want you to help them find the correct pattern, so they can
collect most coins.

    You are given a sequence of numbers, the coins in the valley, and a set of patterns. The coins in the
valley are numbers from -1000 to 1000, meaning the dwarfs should either get 1000 coins, or leave 1000
coins. The set of patterns is represented as many arrays, each containing numbers.

    The patterns consist of numbers and show where the dwarfs should go from their current position in the
valley. The dwarfs should follow the patterns exactly.

    You can use this visualization:

The pattern is used as follows:

    Start from the first number in the valley (valley[0]) and add the number to the coins collected. Then use

the first number in the pattern (pattern[0]) and go to position (0 + pattern[0]) in the valley. Collect the

coins from position 0 + pattern [0] and go to position (0 + pattern[0]) + pattern[1]m collect the coins,

etc…

    When all the numbers from the pattern are used, start the pattern from the top.

    The dwarfs escape the valley when they step on already visited position in the valley, or when they go

out the valley (i.e. their current position + the number in the pattern is leading outside of the valley).

    Help the dwarfs and find the best pattern to use, so they can collect most coins.

Input

The input data should be read from the console.

On the first line you will be given the valley - numbers separated with “, ” (comma and space).

On the second line you will be given M – the number of patterns.

On each of the next M lines you will be given numbers, separated with “, “(comma and space),

representing the patterns.

Output

The output data should be printed on the console.

The output should contain the maximal number of coins, that the dwarfs can collect using one of the

patterns

Constraints

• The numbers in the valley will be between 1 and 10 000 inclusive.

• M will be between 1 and 500

• Each pattern will contain at most 100 numbers

• Each of the numbers in the valley or in the patterns will be between -1000 and 1000

• Allowed work time for your program: 0.1 seconds.

• Allowed memory: 16 MB.

Example:

Input example:

1,3, -6, 7, 4 ,1, 12

3

1,2, -3

1,3, -2

1,-1

Output example:

21

You can find my solution with some explanations  click here... I know very well that I repeat some code, but my time was limited and I just needed this code runing.