using System; using System.Collections.Generic; using System.Linq; namespace No1_3 { public class Program { public struct Input { public int Before { get; } public int After { get; } public int Cost { get; } public int Time { get; } public Input(int before, int t, int cost, int time) { Before = before; After = t; Cost = cost; Time = time; } } public struct Dp { public int Cost { get; } public int Time { get; } public Dp(int cost, int time) { Cost = cost; Time = time; } } public static void Main(string[] args) { var n = Read(Convert.ToInt32);//街の数 var c = Read(Convert.ToInt32);//所持金 var v = Read(Convert.ToInt32);//道の数 var sn = ReadList(Convert.ToInt32);//街A var tn = ReadList(Convert.ToInt32);//街B var yn = ReadList(Convert.ToInt32);//街A → B へのコスト var mn = ReadList(Convert.ToInt32);//街A → B への時間 var inputList = new List(); for(var i = 0; i < v; i++) { inputList.Add(new Input(sn[i], tn[i], yn[i], mn[i])); } inputList.Sort((x, y) => x.Before - y.Before); var dpList = new List[n + 1]; for(var i = 0; i < dpList.Length; i++){ dpList[i] = new List(); } dpList[1].Add(new Dp(0, 0)); foreach(var input in inputList){ foreach(var dp in dpList[input.Before].Where(dp => dp.Cost + input.Cost <= c)){ var tmp = new Dp(dp.Cost + input.Cost, dp.Time + input.Time); if(!dpList[input.After].Exists(d => (d.Cost <= tmp.Cost) && (d.Time <= tmp.Time))){ dpList[input.After].Add(tmp); } } }//(> <) var result = dpList[n].Select(dp => dp.Time).Concat(new []{int.MaxValue}).Min(); Console.WriteLine(result == int.MaxValue ? -1 : result); } public static TOutput Read(Converter converter) { return converter(Console.ReadLine()); } public static List ReadList(Converter converter, char c = ' ') { return Console.ReadLine()?.Split(c).ToList().ConvertAll(converter); } } }