using System; using System.Linq; using System.Text; using System.Collections.Generic; using STR = System.String; using INT = System.Int32; using DEC = System.Double; class Program { public static IO IO = new IO(); public struct DATA { public INT N; public INT T; public INT Y; public INT M; public DATA(INT n, INT t, INT y, INT m) { N = n; T = t; Y = y; M =m; } public bool SAME(DATA t) { return T == t.T && Y == t.Y; } } static void Main(string[] args) { INT n = IO.I(); INT c = IO.I(); INT v = IO.I(); INT[] s = IO.I(' '); INT[] t = IO.I(' '); INT[] y = IO.I(' '); INT[] m = IO.I(' '); INT[] tmin = new INT[v]; Dictionary> data = new Dictionary>(); QUEUE que = new QUEUE(v); for (int i = 0; i < v; i++) { if (!data.Keys.Contains(s[i])) { data[s[i]] = new List(); } data[s[i]].Add(new DATA(i, t[i], y[i], m[i])); tmin[i] = INT.MaxValue; } for (int i = 0; i < data[1].Count(); i++) { que.PUSH(data[1][i]); } while (que.SIZE() != 0) { DATA x = que.POP(); if ((x.Y <= c) && (tmin[x.T - 1] > x.M)) { tmin[x.T - 1] = x.M; } if (data.ContainsKey(x.T)) { for (int i = 0; i < data[x.T].Count(); i++) { DATA buf = data[x.T][i]; if ((buf.Y + x.Y <= c) && (tmin[buf.T - 1] > buf.M + x.M)) { que.PUSH(new DATA(buf.N, buf.T, buf.Y + x.Y, buf.M + x.M)); } } } } INT o = -1; if (tmin[n - 1] != INT.MaxValue) { o = tmin[n - 1]; } IO.W(o); IO.F(); } } public class QUEUE { protected INT m; private INT s, e, c; private T[] q; public QUEUE(INT max) { m = max; q = new T[m]; CLEAR(); } public void CLEAR() { e = 0; s = 0; c = 0; } public INT SIZE() { return c; } public T TOP() { return q[s]; } public T POP() { T r = q[s++]; s %= m; c--; return r; } public virtual void PUSH(T v) { q[e++] = v; e %= m; c++; } public bool EMPTY() { return SIZE() == 0; } } public class IO { private const int WMAX = 1000; private StringBuilder SB = new StringBuilder(); private T R(Func f) { return f(Console.ReadLine()); } private T[] R(Func f, char c) { return S().Split(c).Select(f).ToArray(); } private T[] R(Func f, INT l) { T[] r = new T[l]; for (INT i = 0; i < l; i++) { r[i] = R(f); } return r; } private T[][] R(Func f, INT l, char c) { T[][] r = new T[l][]; for (INT i = 0; i < l; i++) { r[i] = R(f, c); } return r; } private void W(Func f, T v, bool lf = true) { SB.Append(f(v)); if (lf) { SB.Append('\n'); } if (SB.Length >= WMAX) { F(); } } public STR S() { return R(s => s); } public STR[] S(char c) { return R(s => s, c); } public STR[] S(INT l) { return R(s => s, l); } public STR[][] S(INT l, char c) { return R(s => s, l, c); } public INT I() { return R(INT.Parse); } public INT[] I(char c) { return R(INT.Parse, c); } public INT[] I(INT l) { return R(INT.Parse, l); } public INT[][] I(INT l, char c) { return R(INT.Parse, l, c); } public DEC D() { return R(DEC.Parse); } public DEC[] D(char c) { return R(DEC.Parse, c); } public DEC[] D(INT l) { return R(DEC.Parse, l); } public DEC[][] D(INT l, char c) { return R(DEC.Parse, l, c); } public void W(object s, bool lf = true) { W(v => v.ToString(), s, lf); } public void F() { Console.Write(SB); SB.Length = 0; } }