using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        int cityCount = int.Parse(Reader.ReadLine());
        int moneyAmount = int.Parse(Reader.ReadLine());
        int roadCount = int.Parse(Reader.ReadLine());
        int[] fromList = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)-1).ToArray();
        int[] toList = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)-1).ToArray();
        int[] moneyCostList = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
        int[] timeCostList = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();

        for (int i = 0; i < roadCount; i++){
            Road r = new Road(fromList[i], toList[i], moneyCostList[i], timeCostList[i]);
            if(!RoadList.ContainsKey(fromList[i])) {
                RoadList.Add(fromList[i], new Dictionary<int, List<Road>>());
            }
            if(!RoadList[fromList[i]].ContainsKey(toList[i])) {
                RoadList[fromList[i]].Add(toList[i], new List<Road>());
            }
            RoadList[fromList[i]][toList[i]].Add(r);
            /*
            if(!RoadList.ContainsKey(toList[i])) {
                RoadList.Add(toList[i], new Dictionary<int, List<Road>>());
            }
            if(!RoadList[toList[i]].ContainsKey(fromList[i])) {
                RoadList[toList[i]].Add(fromList[i], new List<Road>());
            }
            RoadList[toList[i]][fromList[i]].Add(r);
            */
        }
        MapState[] map = new MapState[cityCount];

        // 0 から CityCount-1 へ行く
        Queue<Task> q = new Queue<Task>();
        q.Enqueue(new Task(0,0));
        map[0] = new MapState();
        map[0].MoneyTime.Add(0, 0);
        while(q.Count()>0) {
            Task t = q.Dequeue();
            int time = map[t.City].MoneyTime[t.Money];

            if(t.City == cityCount-1) {
                continue;
            }
            if(!RoadList.ContainsKey(t.City)) {
                continue;
            }
            foreach(int nextCity in RoadList[t.City].Keys) {
                if(nextCity == 0) {
                    continue;
                }
                foreach(Road r in RoadList[t.City][nextCity]) {
					int nextTime = time + r.TimeCost;
					int nextMoney = t.Money + r.MoneyCost;
					if (nextMoney > moneyAmount)
					{
						continue;
					}
					if (map[nextCity] != null)
					{
						if (map[nextCity].MoneyTime.Any(a => a.Key <= nextMoney && a.Value <= nextTime))
						{
							continue;
						}
						if (map[nextCity].MoneyTime.ContainsKey(nextMoney) && map[nextCity].MoneyTime[nextMoney] <= nextTime)
						{
							continue;
						}
					}
					if (map[nextCity] == null)
					{
						map[nextCity] = new MapState();
					}
					map[nextCity].MoneyTime[nextMoney] = nextTime;
					q.Enqueue(new Task(nextCity, nextMoney));
				}
            }
        }
        int ans = -1;
        if(map[cityCount-1] !=null) {
            ans = map[cityCount - 1].MoneyTime.Min(a => a.Value);
        }
        Console.WriteLine(ans);
    }

    private class Task {
        public int City;
        public int Money;
        public Task(int c,int m) {
            this.City = c;
            this.Money = m;
        }
    }
    private class MapState {
        public Dictionary<int, int> MoneyTime = new Dictionary<int, int>();
    }

    private Dictionary<int, Dictionary<int, List<Road>>> RoadList = new Dictionary<int, Dictionary<int, List<Road>>>();

    private class Road {
        public int City1;
        public int City2;
        public int MoneyCost;
        public int TimeCost;
        public Road(int city1, int city2, int money, int time) {
            this.City1 = city1;
            this.City2 = city2;
            this.MoneyCost = money;
            this.TimeCost = time;
        }
    }

    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"





39
297
167
18 23 2 11 30 15 26 30 29 11 22 4 1 27 14 28 1 33 30 31 36 13 38 25 17 25 30 8 3 29 25 4 34 8 15 4 15 12 2 35 2 27 24 4 10 25 8 18 37 22 19 22 31 22 5 10 38 14 9 29 23 11 3 11 19 7 35 2 16 2 15 33 38 18 26 15 28 6 8 33 10 11 14 30 33 32 18 17 24 35 38 14 18 26 8 15 12 30 32 24 31 9 3 22 21 32 14 37 31 4 31 32 18 30 28 14 29 28 14 18 36 3 18 14 25 16 34 7 15 30 9 29 27 12 24 33 35 37 13 16 18 11 9 1 1 24 13 26 35 36 8 24 15 17 13 19 3 38 11 13 36 7 29 2 36 22 15
21 30 30 18 31 17 37 33 36 32 32 36 12 28 26 30 37 38 37 32 39 31 39 29 35 34 32 31 14 32 28 39 39 37 35 26 28 30 7 38 6 33 31 15 37 34 21 32 38 37 34 36 37 24 34 32 39 22 24 32 33 20 28 28 20 17 38 7 26 21 39 39 39 31 38 24 33 30 36 39 34 34 23 35 37 36 26 29 38 36 39 24 27 34 23 30 25 38 39 38 38 12 30 28 22 34 21 38 34 28 35 33 29 35 33 38 36 36 23 32 38 19 26 17 28 18 37 10 37 38 35 39 32 31 26 37 39 38 38 36 26 24 13 12 11 37 29 31 36 39 39 35 28 24 28 21 39 39 34 18 38 24 35 18 38 30 37
59 145 297 152 137 193 186 145 183 283 136 138 51 225 261 269 18 200 5 211 291 100 151 244 169 194 64 275 260 170 72 276 99 153 166 131 266 10 289 87 124 192 125 90 134 127 36 168 17 96 252 240 293 26 263 154 145 107 170 120 109 263 147 211 207 187 109 26 101 153 169 189 34 97 161 195 20 134 205 92 214 136 268 88 249 280 79 286 155 63 200 202 141 102 243 87 154 165 84 146 67 99 51 86 152 55 27 8 13 3 25 207 90 95 102 160 274 171 127 272 135 31 149 105 259 53 124 57 176 112 231 221 14 131 131 195 175 182 142 127 174 97 274 251 80 65 260 217 63 294 123 4 255 283 245 239 3 56 222 218 217 248 241 122 138 259 210
356 518 175 730 104 843 67 682 891 309 625 302 960 446 881 698 776 193 956 630 894 423 778 577 707 378 413 961 423 507 649 871 283 66 649 731 913 697 972 345 709 421 191 975 356 125 83 257 334 634 184 844 598 992 727 139 845 414 335 656 360 533 231 460 943 281 982 543 473 775 94 565 225 995 550 974 939 233 63 798 757 256 854 898 581 421 400 719 328 961 503 674 104 291 692 138 115 690 475 106 741 924 977 997 373 501 308 587 217 805 394 264 650 403 66 12 247 80 652 25 516 1 94 895 476 990 122 739 263 42 282 256 73 890 435 142 248 28 924 681 503 431 882 948 191 974 908 867 216 487 14 771 536 840 615 481 830 248 484 422 779 332 848 145 365 11 453







";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}