/* package whatever; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Main { public static void main (String[] args) throws java.lang.Exception { // your code goes here BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] lines = br.readLine().split(" "); int gx = Integer.parseInt(lines[0]); int gy = Integer.parseInt(lines[1]); int n = Integer.parseInt(lines[2]); int f = Integer.parseInt(lines[3]); Place start = new Place(0,0); Place goal = new Place(gx,gy); ArrayList crystals = new ArrayList(); for(int i=0;i queue = new PriorityQueue(1, new Comparator(){ public int compare(Place p1,Place p2){ if(p1.c!=p2.c){ return p1.c-p2.c; } return p2.x+p2.y - p1.x - p1.y; } }); queue.add(start); HashMap routemap = new HashMap(); while(!queue.isEmpty()){ Place now = queue.poll(); if(now.x == goal.x && now.y == goal.y){ goal = now; break; } for(Crystal c:crystals){ if(now.canUseCrystal(c)){ Place newPlace = now.clone(); newPlace.useCrystal(c); String key = newPlace.x + "_" + newPlace.y; if(newPlace.x <= goal.x && newPlace.y <= goal.y && (!routemap.containsKey(key) || routemap.get(key)>newPlace.c)){ queue.add(newPlace); routemap.put(key,newPlace.c); } } } Place newPlace = now.clone(); newPlace.move(goal,f); queue.add(newPlace); } System.out.println(goal.c); } private static class Place{ int x,y; int c; ArrayList useCrystal = new ArrayList(); public Place(int x,int y){ this.x = x; this.y = y; this.c = 0; } public Place clone(){ Place p = new Place(this.x,this.y); p.c = this.c; for(int n:this.useCrystal){ p.useCrystal.add(n); } return p; } public boolean canUseCrystal(Crystal c){ return useCrystal.indexOf(c.no)==-1; } public void useCrystal(Crystal c){ this.x += c.x; this.y += c.y; this.c += c.c; useCrystal.add(c.no); } public void move(Place g,int f){ int cost = f*(g.x-this.x); cost += f*(g.y-this.y); this.x = g.x; this.y = g.y; this.c += cost; } } private static class Crystal{ public int no; public int x,y,c; public Crystal(int no,String line){ this.no = no; String[] lines = line.split(" "); this.x = Integer.parseInt(lines[0]); this.y = Integer.parseInt(lines[1]); this.c = Integer.parseInt(lines[2]); } } }