Problem P
Energy Usage

The price of electricity energy fluctuates depending on supply and demand. As the manager of a 24-hour factory producing widgets, Homer wants to minimize the energy cost to operate the factory. Homer has no ability to control the price, nor can he change the amount of energy required to produce widgets. However, the factory has some solar panels installed which convert sunlight into energy. Homer is considering purchasing a battery of capacity $B$ Megawatt-hour (MWh) so he can store energy for use later. He would like to know if such a purchase makes financial sense.

Using past data, Homer predicts the following information for the next $N$ hours ($1 \leq i \leq N$ below):

• $p_i$: the price of energy (in dollars/MWh) for the $i$-th hour

• $r_i$: the amount of energy (in MWh) required to operate the factory for the $i$-th hour

• $s_i$: the amount of energy (in MWh) generated by solar panels for the $i$-th hour

Furthermore, Homer assumes the battery is initially empty.

For each hour, Homer can decide to do one or more of the following actions to satisfy the energy requirement for that hour:

• use some amount of solar energy generated

• use some amount of battery energy stored

• purchase energy from the power company, paying $p_i$ per MWh purchased

After fulfilling the energy requirements for the hour, Homer can also choose to do one or more of the following actions:

• store some amount of the excess energy (combined from excess solar energy, excess purchased energy, and stored battery energy) into the battery, up to the battery capacity.

• sell some amount of the excess energy. Each hour, the power company has $M$ energy buyback plans. For the $j$-th buyback plan, Homer can sell exactly exactly $d_{i,j}$ MWh for $c_{i,j}$. Up to one plan can be chosen per hour.

• waste some amount of the excess energy.

Help Homer determine the minimum cost to operate the factory for the next $N$ hours. Any energy left in the battery at the end of the $N$-th hour is considered wasted. A negative cost means that Homer can make a profit.

Input

The first line contains three integers $N$ $(1 \leq N \leq 1\, 000)$, $M$ $(1 \leq M \leq 10)$, and $B$ $(1 \leq B \leq 20)$, where $N$ is the number of hours, $M$ is the number of buyback plans available for each hour, and $B$ is capacity of the battery.

Each of the next $N$ lines contains three integers, $p_i$, $r_i$, and $s_i$ $(1 \leq p_i, r_i, s_i \leq 100)$, where $p_i$ is the price of energy for the $i$-th hour, $r_i$ is the energy required to operate the factory for the $i$-th hour, and $s_i$ is the amount of solar energy generated for the $i$-th hour.

Each of the next $N$ lines contains $M$ integers, $1 \leq c_{i,j} \leq 10\, 000$, where $c_{i,j}$ is the price for the $j$-th buyback plan for the $i$-th hour.

Each of the next $N$ lines contains $M$ integers, $1 \leq d_{i,j} \leq 100$, where $d_{i,j}$ is the amount of energy (in MWh) that can be sold for the $j$-th buyback plan for the $i$-th hour.

Output

Output the minimum cost required to operate the factory for the next $N$ hours.

2 1 10
4 3 3
1 5 3
4
9
2
3

-4

3 4 5
1 5 3
9 4 3
10 6 3
1 3 4 9
1 3 6 9
1 3 6 30
1 2 3 4
1 2 3 4
1 2 3 4

1

3 2 2
1 3 6
4 6 3
10 6 3
4 10
2 9
10 20
1 10
2 4
1 3

18