import java.util.*;
public class Main{

    static int N = 1010;
    static int f[] = new int[N];
    static int l[] = new int[N], h[] = new int[N], v[] = new int[N], w[] = new int[N];
    static int n, m, v0, w0;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        v0 = sc.nextInt();
        w0 = sc.nextInt();

        // 第0个物品在满足体积要求的情况下可以装无数个，是完全背包问题
        for(int i = v0; i <= m; i++) f[i] = Math.max(f[i], f[i - v0] + w0);

        for(int i = 1; i <= n; i++){
            l[i] = sc.nextInt();
            h[i] = sc.nextInt();
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        // 后面的n个物品是多重背包问题，每个物品最多可以选 l/h 个
        for(int i = 1; i <= n; i++){
            for(int j = m; j > 0; j--){
                for(int k = 0; k <= l[i] / h[i] && k * v[i] <= j; k++){
                    f[j] = Math.max(f[j], f[j - k * v[i]] + k * w[i]);
                }
            }
        }
        System.out.println(f[m]);
        sc.close();
    }
}

import java.io.*;
import java.util.*;

public class Main {

    static int N = 510, M = 6010;
    static int f[][] = new int[N][M];
    static int v[] = new int[N], w[] = new int[N], s[] = new int[N];
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer stmInput = new StreamTokenizer(br);
        stmInput.nextToken();
        n = (int)stmInput.nval;
        stmInput.nextToken();
        m = (int)stmInput.nval;
        for(int i = 1; i <= n; i++){
            stmInput.nextToken();
            v[i] = (int)stmInput.nval;
            stmInput.nextToken();
            w[i] = (int)stmInput.nval;
            stmInput.nextToken();
            s[i] = (int)stmInput.nval;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= s[i] && k * v[i] <= j; k++){
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }
        System.out.println(f[n][m]);
        br.close();
    }
}

// f[i][j]: 在前i个数中选且总和恰好为j的所有选法的集合
// 属性: 所有选法的数量cnt
import java.util.*;
public class Main{

    static int N = 10010;
    static int f[] = new int[N];
    static int v[] = new int[N];
    static int n, m;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
        }
        // f[0][0] = 1; f[0][j] = 0
        f[0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = m; j >= v[i]; j--){
                f[j] += f[j - v[i]];
            }
        }
        System.out.println(f[m]);
        sc.close();
    }

}

import java.io.*;
import java.util.*;

public class Main {

    static int N = 22, M = 80, INF = (int)1e9;
    static int f[][] = new int[N][M];
    static int n, m, k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StreamTokenizer stmInput = new StreamTokenizer(br);
        stmInput.nextToken();
        n = (int)stmInput.nval;
        stmInput.nextToken();
        m = (int)stmInput.nval;
        stmInput.nextToken();
        k = (int)stmInput.nval;

        for(int i = 0; i < N; i++) Arrays.fill(f[i], INF);
        f[0][0] = 0; // 一个都不选的重量为0

        // 在前i个物品中选且总v1至少为j，总v2至少为k的所有选法的集合
        // 最小重量
        while(k-- != 0){
            stmInput.nextToken();
            int v1 = (int)stmInput.nval;
            stmInput.nextToken();
            int v2 = (int)stmInput.nval;
            stmInput.nextToken();
            int w = (int)stmInput.nval;
            for(int j = n; j >= 0; j--){
                for(int k = m; k >= 0; k--){
                    f[j][k] = Math.min(f[j][k], f[Math.max(0, j - v1)][Math.max(0, k - v2)] + w);
                }
            }
        }
        System.out.println(f[n][m]);
        bw.flush();
        bw.close();
        br.close();
    }
}

import java.io.*;
import java.util.*;

public class Main {

    static int N = 1010, G = 110;
    static int f[][] = new int[G][G];
    static int v[] = new int[N], m[] = new int[N], w[] = new int[N];
    static int n, V, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer stmInput = new StreamTokenizer(br);
        stmInput.nextToken();
        n = (int)stmInput.nval;
        stmInput.nextToken();
        V = (int)stmInput.nval;
        stmInput.nextToken();
        M = (int)stmInput.nval;
        for(int i = 1; i <= n; i++){
            stmInput.nextToken();
            v[i] = (int)stmInput.nval;
            stmInput.nextToken();
            m[i] = (int)stmInput.nval;
            stmInput.nextToken();
            w[i] = (int)stmInput.nval;
        }

        for(int i = 1; i <= n; i++){
            for(int j = V; j >= v[i]; j--){
                for(int k = M; k >= m[i]; k--){
                    f[j][k] = Math.max(f[j][k], f[j - v[i]][k - m[i]] + w[i]);
                }
            }
        }
        System.out.println(f[V][M]);
        br.close();
    }
}

import java.io.*;
import java.util.*;

public class Main {

    static int N = 1010, M = 510;
    static int f[][] = new int[N][M];
    static int v1[] = new int[N], v2[] = new int[M];
    static int n, V1, V2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer stmInput = new StreamTokenizer(br);
        stmInput.nextToken();
        V1 = (int)stmInput.nval;
        stmInput.nextToken();
        V2 = (int)stmInput.nval;
        stmInput.nextToken();
        n = (int)stmInput.nval;
        for(int i = 1; i <= n; i++){
            stmInput.nextToken();
            v1[i] = (int)stmInput.nval;
            stmInput.nextToken();
            v2[i] = (int)stmInput.nval;
        }

        // 二维费用的背包问题
        for(int i = 1; i <= n; i++){
            for(int j = V1; j >= v1[i]; j--){
                // 皮卡丘的体力值不能减少为0，所以k从V2-1开始
                for(int k = V2 - 1; k >= v2[i]; k--){
                    f[j][k] = Math.max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);
                }
            }
        }
        System.out.print(f[V1][V2 - 1] + " ");

        // 在能收服的小精灵最多的情况下，小精灵的体力值之和最少是多少？
        // 也就能求出皮卡丘所剩体力值的最大值。
        int k = V2 - 1; // k为小精灵体力值之和，最大为V2-1
        while(k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k--;
        System.out.print(V2 - k);

        br.close();
    }
}

import java.util.*;
public class Main{

    static int N = 35, M = 20010;
    static int f[] = new int[N * M];
    static int v[] = new int[N];
    static int n, m;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        for(int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
        }

        for(int i = 1; i <= n; i++){
            for(int j = m; j >= v[i]; j--){
                f[j] = Math.max(f[j], f[j - v[i]] + v[i]);
            }
        }        
        System.out.println(m - f[m]);        
        sc.close();
    }
}

import java.util.*;
public class Main{

    static int N = 1010;
    static int f[] = new int[N];
    static int v[] = new int[N], w[] = new int[N];
    static int n, m;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        for(int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for(int i = 1; i <= n; i++){
            for(int j = m; j >= v[i]; j--){
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
            }
        }        
        System.out.println(f[m]);        
        sc.close();
    }
}

import java.io.*;
import java.util.*;

public class Main {

    static class Cow{
        int w, s;
        public Cow(int w, int s){
            this.w = w;
            this.s = s;
        }
    }
    static int N = 50010;
    static Cow cows[] = new Cow[N];
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer stmInput = new StreamTokenizer(br);
        stmInput.nextToken();
        n = (int)stmInput.nval;
        for(int i = 0; i < n; i++){
            stmInput.nextToken();
            int w = (int)stmInput.nval;
            stmInput.nextToken();
            int s = (int)stmInput.nval;
            cows[i] = new Cow(w, s);
        }
        // 按w+s从小到大排序
        Arrays.sort(cows, 0, n, (a, b) -> {return a.w + a.s - b.w - b.s;});
        // 计算最大危险值
        long res = (long)-2e9, sum = 0;
        for(int i = 0; i < n; i++){
            res = Math.max(res, sum - cows[i].s);
            sum += cows[i].w;
        }
        System.out.println(res);
        br.close();
    }
}

import java.io.*;
import java.util.*;

public class Main {

    static int N = 100010;
    static int a[] = new int[N];
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer stmInput = new StreamTokenizer(br);
        stmInput.nextToken();
        n = (int)stmInput.nval;
        for(int i = 0; i < n; i++){
            stmInput.nextToken();
            a[i] = (int)stmInput.nval;
        }
        Arrays.sort(a, 0, n);

        long res = 0;
        for(int i = 0; i < n; i++) res += Math.abs(a[i] - a[n / 2]);
        System.out.println(res);
        br.close();
    }
}