package main; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Scanner; public class Main { private static int[] arr; private int[][] ar2; private List list; public static int n,m,k; private static HashSet set; private static HashMap map; private static Scanner sc = new Scanner(System.in); private static List> ll; private static List> hList; public static void main(String[] args){ //n = sc.nextInt(); //arr = new int[n]; int Gx = sc.nextInt(); int Gy = sc.nextInt(); n = sc.nextInt(); int F = sc.nextInt(); // int[][] dp = new int[101][101]; // for(int i=0 ; i<101; i++)dp[i ] = new int[101]; Crystal[] stone = new Crystal[n]; //List>edge = new ArrayList>(); //for(int i=0; i<=n; i++)edge[i] = new ArrayList()>() ; for(int i=0; i>j)&1) == 1){ x += stone[j].x; y += stone[j].y; cost += stone[j].c; } } if(x>Gx || y>Gy)continue; //int dis = Math.abs(Gx-x)+Math.abs(Gy-y); //int com = Math.abs(memo[0]-x)+Math.abs(memo[1]-y); int dis = calc(x, y, cost, Gx, Gy, F); int com = calc(memo[0], memo[1], memo[2], Gx, Gy, F); if(dis> list; public UnionFind (int n, int[] original) { path = new int[n+1]; size = new int[n+1]; list = new ArrayList>(); for(int i=0; i()); list.get(i).add(original[i]); } } public int root(int i){ while (path[i] != i) { path[i] = path[path[path[i]]]; i = path[i]; } return i; } public boolean find(int p, int q) { if(p<0 || q<0)return false; return root(p) == root(q); } public void uniite(int p, int q) { if(p<0 || q<0)return; int i = root(p); int j = root(q); if(i==j)return; if(size[i]>size[j]){ // int tmp = i;l // i=j; // j = tmp; i^=j^=i^=j; } size[j ] += size[i]; path[i] = j; } } class BIT{ int n; private int[] bit = new int[100010]; public BIT(int x , int[] original){ this.n = x; for(int i=1; i<=n; i++){ //bit[i] = original[i]; add(i, original[i]); } } public void add(int a, int w) { for(int i = a; i<=n; i+= i&(-i))bit[i] +=w; } public int sum(int a) { int sum = 0; for(int i=a;i>0; i-=i&(-i)) sum+=bit[i]; return sum; } public int binary(int w){ if(w<=0)return 0; int x =0; for(int k = n%2==0? n:n-1; k>0; k/=2){ if(x+k<=n && bit[x+k][] dat; public Segment(int x) { this.n = x; this.size = x*2; dat = new int[size]; //dat = new HashSet[size]; for(int i=0; i(); } } public void update(int i, int x) { i = n+i-1; dat[i ] = x; while (i>0) { i =(i-1)/2; dat[i] = Math.min(dat[i*2+1], dat[i*2+2]); } } int query(int a, int b, int k, int l, int r){ if(r<=a || b<=l)return Integer.MAX_VALUE; if(a<=l && r<=b)return dat[k]; else { int vl = query(a, b, k*2+1, l, (l+r)/2); int vr = query(a, b, k*2+2, (l+r)/2, r); return Math.min(vl, vr); } } } class Tree{ int n,l ; private int[][] g; private int[] tin,tout; int timer; private int[][] up; public Tree(int n){ this.n = n; tin = new int[n+1]; tout = new int[n+1]; timer = 0; g= new int[n+1][l]; up = new int[n+1][l]; l = 1; while ((1 << l) <= n) ++ l; //for (int i = 0; i = tout [b]; } int lca (int a, int b) { if (upper (a, b)) return a; if (upper (b, a)) return b; for (int i = l; i>= 0; --i) if (! upper (up [a] [i], b)) a = up [a] [i]; return up [a] [0]; } } //class Tree{ // int n,l ; // private int[][] g; // private int[] tin,tout; // int timer; // private int[][] up; // private int[] parent ; // // public Tree(int n){ // this.n = n; // this.l = (int)Math.pow(2,n); // tin = new int[n+1]; // tout = new int[n+1]; // timer = 0; // parent = new int[n+1]; // g= new int[n+1][n+1]; // up = new int[n+1][n+1]; // for(int i=0; i<=n; i++){ // g[i] = new int[n+1]; // up[i]= new int[n+1]; // } // } // // void preprocess(){ // //Every element in P[][] is -1 initially; // for(int i = 1 ; i <= n ; ++i){ // for(int j = 0 ; (1< 0){ // int raise_by = log2(dist); // u = P[u][raise_by]; // dist -= (1<= 0 ; --j){ // //Checking P[u][j] != P[v][j] because if P[u][j] == P[v][j] // //P[u][j] would be the Lth ancestor such that (L >= k) // //where kth ancestor is the LCA // //But we want the (k-1)th ancestor. // if((P[u][j] != -1) and (P[u][j] != P[v][j])){ // u = P[u][j] ; // v = P[v][j] ; // } // } // return parent[u] ; //or parent[v] // } //}