高性能計算機

p個のノードを持つ大型計算機がある.この計算機をうまく使って,与えられたタスクをなるべく早く完了させたい.
タスクはAとBの2種類であり,同じ種類に属するタスクは全く同じものである.
計算能力はノードによって異なる.計算機の仕様は以下の通りである.
1. すべてのノードは3種類の状態がある.それぞれIdle, State A, State Bであり, 
 Idle状態のときには計算を実行しない.最初はすべての計算機がIdle状態である.
 State AではAのタスクを実行する.State BではBのタスクを実行する.
 Idle状態以外からA,Bの状態に移行するには,それぞれtA, tBのスタート時間がかかる.この値はノード毎に異なる.

2.1つのノードが連続して同じ種類のタスクを実行する場合,そのタスクの個数の二乗と
 ノードとタスクの種類で決まる定数の積の時間がかかる.
 すなわちi番目のノードがAのタスクをx個連続で実行した場合の実行時間:t = kAi * x^2
 同様に, i番目のノードがBのタスクをx個連続で実行した場合の実行時間:t = kBi * x^2

それぞれのノードは並列に動くため,タスクを割り振ることは,各ノードにAとBで構成された文字列を与えることと同じである.
文字列はAとBが入り組んでいてもかまわない.

同じ種類のタスクは,いったん複数個割り当てたらそれを全部実行しなければならない.
例えば,1つのノードで連続する4個のAを,A2個ずつに分けて実行することはできない.
Input
入力は以下の形式で与えられる.
	nA nB
	p
	tA1 tB1 kA1 kB1
	tA2 tB2 kA2 kB2
	tA3 tB3 kA3 kB3
	...
	tAp tBp kAp kBp
nA, nBはそれぞれA,Bのタスクの数である.(1<=nA<=60, 1<=nB<=60)
pは計算ノードの数である.(1<=p<=20)
tA, tBiはスタートにかかる時間(1<=tA<=1000, 1<=tB<=1000)であり,kAi,kBiは上記の定数である.(1<=kA<=50, 1<=kB<=50)

Output
タスクを割り振ったときにかかる所要時間の最小値を1行で出力.

Sample Input
5 5
3
15 10 6 4
70 100 7 2
30 70 1 6

Sample Output
93

出典 IOI2001 National Training Team Winter Camp. Problem　2．HPC.