lntanx は農場に尿素肥料を納品する仕事をしている。ある農場から注文が入り、その肥料を作るにはアンモニアが 缶必要になった。倉庫にアンモニアが残っていないため、窒素と水素を購入してアンモニアを合成することにした。
一回の合成では窒素 缶と水素 缶を使い、アンモニア 缶を得る。合成そのものに費用はかからない。合成は整数回行い、必要量を超えて生産してもよい。
窒素の供給元は か所、水素の供給元は か所ある。各供給元の在庫量と一缶当たりの価格が与えられる。各供給元から在庫量以下の整数缶を購入でき、同じ原料を複数の供給元から分けて購入してもよい。
アンモニアを 缶以上得るために必要な原料の購入費用の最小値を求めよ。
一行目に窒素の供給元の数 、水素の供給元の数 、必要なアンモニアの量 が空白区切りで与えられる。
続く 行には窒素の供給元の情報が一行ずつ与えられる。その後の 行には水素の供給元の情報が一行ずつ与えられる。各供給元について、在庫量 と一缶当たりの価格 が空白区切りで与えられる。
一行目に最小費用を出力せよ。原料が足りずアンモニアを 缶以上作れない場合は -1 を出力せよ。
費用の計算には符号付き 64 ビット整数型の使用を推奨する。
窒素を一つ目の供給元から 缶、二つ目から 缶買うと費用は になる。水素を一つ目の供給元から 缶、二つ目から 缶買うと費用は になる。この原料でアンモニアを 缶合成できる。