using System;
using System.Collections.Generic;
using System.Linq;
// https://atcoder.jp/contests/past202005-open/tasks/past202005_o
class Program
{
static string InputPattern = "Input1";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("2 1");
WillReturn.Add("3 2");
WillReturn.Add("3 3");
WillReturn.Add("100000 100000 100000");
//81
}
else if (InputPattern == "Input2") {
WillReturn.Add("4 2");
WillReturn.Add("2 4 3 3");
WillReturn.Add("4 2 3 3");
WillReturn.Add("100000 100000 100000");
//210
}
else if (InputPattern == "Input3") {
WillReturn.Add("20 19");
WillReturn.Add("3 2 3 4 3 3 2 3 2 2 3 3 4 3 2 4 4 3 3 4");
WillReturn.Add("2 3 4 2 4 3 3 2 4 2 4 3 3 2 3 4 4 4 2 2");
WillReturn.Add("3 4 5");
//-1417
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
class EdgeInfoDef
{
internal long ToNode;
internal long Capacity;
internal long Cost;
internal long Flow;
}
static Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict = new Dictionary<long, List<EdgeInfoDef>>();
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(InputList[0]);
long N = wkArr[0];
long M = wkArr[1];
long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long[] BArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(InputList.Last());
long R1 = wkArr[0];
long R2 = wkArr[1];
long R3 = wkArr[2];
var NodeNameList = new List<string>();
NodeNameList.Add("R1");
NodeNameList.Add("R2");
NodeNameList.Add("R3");
for (long I = 1; I <= N; I++) {
NodeNameList.Add("棒" + I.ToString());
}
NodeNameList.Add("Source");
NodeNameList.Add("Sink");
// ノードID[ノード名]なDict
var NodeIDDict = new Dictionary<string, long>();
foreach (string EachStr in NodeNameList) {
NodeIDDict[EachStr] = NodeIDDict.Count;
}
long UB = NodeIDDict.Count - 1;
Action<long, long, long, long> AddEdgeAct = (pFromNode, pToNode, pCapacity, pCost) =>
{
if (mEdgeInfoListDict.ContainsKey(pFromNode) == false) {
mEdgeInfoListDict[pFromNode] = new List<EdgeInfoDef>();
}
var WillAdd = new EdgeInfoDef();
WillAdd.ToNode = pToNode;
WillAdd.Capacity = pCapacity;
WillAdd.Cost = pCost;
WillAdd.Flow = 0;
mEdgeInfoListDict[pFromNode].Add(WillAdd);
};
AddEdgeAct(NodeIDDict["Source"], NodeIDDict["R1"], M, 0);
AddEdgeAct(NodeIDDict["Source"], NodeIDDict["R2"], M, 0);
AddEdgeAct(NodeIDDict["Source"], NodeIDDict["R3"], M, 0);
AddEdgeAct(NodeIDDict["R1"], NodeIDDict["Source"], 0, 0);
AddEdgeAct(NodeIDDict["R2"], NodeIDDict["Source"], 0, 0);
AddEdgeAct(NodeIDDict["R3"], NodeIDDict["Source"], 0, 0);
for (long I = 1; I <= 3; I++) {
long FromNode = NodeIDDict["R" + I.ToString()];
for (long J = 1; J <= N; J++) {
long ToNode = NodeIDDict["棒" + J.ToString()];
long Syokou = AArr[J - 1];
long Kouhi = BArr[J - 1];
long Cost = Syokou * Kouhi;
for (long K = 1; K <= I; K++) {
Cost *= Kouhi;
}
long Hou = R1;
if (I == 2) Hou = R2;
if (I == 3) Hou = R3;
AddEdgeAct(FromNode, ToNode, 1, -1 * (Cost % Hou));
AddEdgeAct(ToNode, FromNode, 0, +1 * (Cost % Hou));
}
}
for (long I = 1; I <= N; I++) {
long FromNode = NodeIDDict["棒" + I.ToString()];
long Syokou = AArr[I - 1];
long Kouhi = BArr[I - 1];
long Cost = Syokou * Kouhi;
var CostList = new List<long>();
for (long J = 1; J <= 3; J++) {
Cost *= Kouhi;
CostList.Add(Cost);
}
for (int J = 0; J <= CostList.Count - 1; J++) {
long CurrCost = CostList[0];
if (J == 1) {
CurrCost = CostList[1] - CostList[0];
}
if (J == 2) {
CurrCost = CostList[2] - CostList[1] - CostList[0];
}
AddEdgeAct(FromNode, NodeIDDict["Sink"], 1, +CurrCost);
AddEdgeAct(NodeIDDict["Sink"], FromNode, 0, -CurrCost);
}
}
// 逆辺と正辺で二重辺が存在しうるので、コストの昇順にソートしておく
foreach (var EachPair in mEdgeInfoListDict) {
EachPair.Value.Sort((pA, pB) => pA.Cost.CompareTo(pB.Cost));
}
long RestFlow = M * 3;
while (RestFlow > 0) {
var NodeList = BellmanFord(NodeIDDict["Source"], NodeIDDict["Sink"]);
if (NodeList == null) {
Console.WriteLine(-1);
return;
}
Console.WriteLine("経路を発見しました");
NodeList.ForEach(pX => Console.Write("{0},", pX));
Console.WriteLine();
// 経路でのCapacityの最小値を求める
var CapacityList = new List<long>();
for (int I = 0; I <= NodeList.Count - 2; I++) {
long FromNode = NodeList[I];
long ToNode = NodeList[I + 1];
foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[FromNode]) {
if (EachEdgeInfo.ToNode != ToNode) continue;
// 二重辺が存在しうるので、Capacityが0ならcontinue
if (EachEdgeInfo.Capacity == 0) continue;
CapacityList.Add(EachEdgeInfo.Capacity);
break;
}
}
long CurrFlow = Math.Min(RestFlow, CapacityList.Min());
Console.WriteLine("この経路に{0}の水を流します", CurrFlow);
// フローを流して、逆辺を作る
for (int I = 0; I <= NodeList.Count - 2; I++) {
long FromNode = NodeList[I];
long ToNode = NodeList[I + 1];
// フローを流す
foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[FromNode]) {
if (EachEdgeInfo.ToNode != ToNode) continue;
// 二重辺が存在しうるので、Capacityが0ならcontinue
if (EachEdgeInfo.Capacity == 0) continue;
EachEdgeInfo.Capacity -= CurrFlow;
EachEdgeInfo.Flow += CurrFlow;
break;
}
// 逆辺を作る
foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[ToNode]) {
if (EachEdgeInfo.ToNode != FromNode) continue;
EachEdgeInfo.Capacity += CurrFlow;
break;
}
}
RestFlow -= CurrFlow;
}
// コストを計算する
long Answer = 0;
foreach (List<EdgeInfoDef> EachEdgeList in mEdgeInfoListDict.Values) {
foreach (EdgeInfoDef EachEdgeInfo in EachEdgeList) {
Answer += EachEdgeInfo.Flow * EachEdgeInfo.Cost;
}
}
Console.WriteLine(Answer);
}
// ベルマンフォードで、最小コストな経路を返す
static List<long> BellmanFord(long pStaNode, long pGoalNode)
{
// どのノードから来たかのDict
var PrevNodeDict = new Dictionary<long, long>();
//各ノードまでの距離のDict
var SumCostDict = new Dictionary<long, long>();
SumCostDict[pStaNode] = 0;
// 頂点数だけループ
bool WillBreak = false;
for (long I = 1; I <= int.MaxValue; I++) {
WillBreak = true;
foreach (long EachKey in SumCostDict.Keys.ToArray()) {
if (mEdgeInfoListDict.ContainsKey(EachKey) == false)
continue;
// そのノードから訪問可能なノードで
// 最短距離を更新可能なら更新
foreach (EdgeInfoDef EachNodeInfo in mEdgeInfoListDict[EachKey]) {
if (EachNodeInfo.Capacity == 0) continue;
long wkSumCost = SumCostDict[EachKey] + EachNodeInfo.Cost;
if (SumCostDict.ContainsKey(EachNodeInfo.ToNode)) {
if (SumCostDict[EachNodeInfo.ToNode] <= wkSumCost) {
continue;
}
}
SumCostDict[EachNodeInfo.ToNode] = wkSumCost;
PrevNodeDict[EachNodeInfo.ToNode] = EachKey;
WillBreak = false;
}
}
if (WillBreak) break;
}
if (SumCostDict.ContainsKey(pGoalNode) == false) {
return null;
}
var NodeList = new List<long>();
long CurrNode = pGoalNode;
while (true) {
NodeList.Add(CurrNode);
if (CurrNode == pStaNode) break;
CurrNode = PrevNodeDict[CurrNode];
}
NodeList.Reverse();
return NodeList;
}
}