Untitled

mail@pastecode.io avatar
unknown
java
a year ago
2.2 kB
3
Indexable
import java.util.Arrays;
import java.util.Scanner;

class Ticket implements Comparable<Ticket> {
    int b;
    int c;
    int max_c;

    public Ticket() {
        this.b = 0;
        this.c = 0;
        this.max_c = 0;
    }

    public Ticket(int b, int c) {
        this.b = b;
        this.c = c;
        this.max_c = 0;
    }

    @Override
    public int compareTo(Ticket other) {
        if (this.b < other.b) {
            return -1;
        } else if (this.b == other.b) {
            return Integer.compare(other.c, this.c);
        } else {
            return 1;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        Ticket[] ts = new Ticket[m];
        for (int i = 0; i < m; i++) {
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            ts[i] = new Ticket(b, c);
        }

        Arrays.sort(ts);

        int max_c = 0;
        for (int i = 0; i < m; i++) {
            ts[i].max_c = Math.max(max_c, ts[i].c);
            if (ts[i].c > max_c) {
                max_c = ts[i].c;
            }
        }

        long res = 0;
        for (int i = 0; i < n; i++) {
            int searchValue = a[i];
            int low = 0;
            int high = m - 1;
            int lastIndex = -1;

            while (low <= high) {
                int mid = (low + high) / 2;
                if (ts[mid].b == searchValue) {
                    lastIndex = mid;
                    break;
                } else if (ts[mid].b < searchValue) {
                    lastIndex = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }

            if (lastIndex == -1) {
                res += a[i] - ts[m - 1].max_c;
            } else {
                res += a[i] - ts[lastIndex].max_c;
            }
        }

        System.out.println(res);
    }
}