The only difference between easy and hard versions is constraints.

Ivan plays a computer game that contains some microtransactions to make characters look cooler. Since Ivan wants his character to be really cool, he wants to use some of these microtransactions — and he won't start playing until he gets all of them.

Each day (during the morning) Ivan earns exactly one burle.

There are n types of microtransactions in the game. Each microtransaction costs 2 burles usually and 1 burle if it is on sale. Ivan has to order exactly k_i microtransactions of the i-th type (he orders microtransactions during the evening).

Ivan can order any (possibly zero) number of microtransactions of any types during any day (of course, if he has enough money to do it). If the microtransaction he wants to order is on sale then he can buy it for 1 burle and otherwise he can buy it for 2 burles.

There are also m special offers in the game shop. The j-th offer (d_j, t_j) means that microtransactions of the t_j-th type are on sale during the d_j-th day.

Ivan wants to order all microtransactions as soon as possible. Your task is to calculate the minimum day when he can buy all microtransactions he want and actually start playing.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 1000) — the number of types of microtransactions and the number of special offers in the game shop.

The second line of the input contains n integers k_1, k_2, ..., k_n (0 ≤ k_i ≤ 1000), where k_i is the number of copies of microtransaction of the i-th type Ivan has to order. It is guaranteed that sum of all k_i is not less than 1 and not greater than 1000.

The next m lines contain special offers. The j-th of these lines contains the j-th special offer. It is given as a pair of integers (d_j, t_j) (1 ≤ d_j ≤ 1000, 1 ≤ t_j ≤ n) and means that microtransactions of the t_j-th type are on sale during the d_j-th day.

Output

Print one integer — the minimum day when Ivan can order all microtransactions he wants and actually start playing.

Examples

Input


5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3


Output


8


Input


5 3
4 2 1 3 2
3 5
4 2
2 5


Output


20

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

public class b
{
    public static void print(String str,long val){
        System.out.println(str+"  "+val);
    }

    public long gcd(long a, long b) {
        if (b==0L) return a;
        return gcd(b,a%b);
    }

    public static void debug(long[][] arr){
        int len = arr.length;
        for(int i=0;i<len;i++){
            System.out.println(Arrays.toString(arr[i]));
        }
    }
    public static void debug(int[][] arr){
        int len = arr.length;
        for(int i=0;i<len;i++){
            System.out.println(Arrays.toString(arr[i]));
        }
    }
    public static void debug(String[] arr){
        int len = arr.length;
        for(int i=0;i<len;i++){
            System.out.println(arr[i]);
        }
    }

    public static void print(int[] arr){
        int len = arr.length;
        for(int i=0;i<len;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.print('\n');
    }

    public static void print(Object[] arr){
        int len = arr.length;
        for(int i=0;i<len;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.print('\n');
    }
    public static void print(String[] arr){
        int len = arr.length;
        for(int i=0;i<len;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.print('\n');
    }
    public static void print(long[] arr){
        int len = arr.length;
        for(int i=0;i<len;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.print('\n');
    }

    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }
        public FastReader(String path) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(path));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

    static void sort(long[] arr){
        Long[] temp = new Long[arr.length];
        for(int i=0;i<arr.length;i++){
            temp[i] = arr[i];
        }
        Arrays.sort(temp);
        for(int i=0;i<arr.length;i++){
            arr[i] = temp[i];
        }
    }

    static int[] copies;
    static pair[] days;
    static int n;
    static int m;
    public static void main(String[] args)
    {
        FastReader s=new FastReader();
        n = s.nextInt();
        m = s.nextInt();
        copies = new int[n];
        for(int i=0;i<n;i++){
            copies[i] = s.nextInt();
        }
        days = new pair[m];
        for (int i=0;i<m;i++){
            int day = s.nextInt();
            int type = s.nextInt()-1;
            days[i] = new pair(day,type);
        }
        Arrays.sort(days);
        int start =1;
        int end = 2*(1000);
        while (end-start>1){
            int mid = (end+start)/2;
            if(check(mid)){
                end = mid;
            }
            else start = mid+1;
        }
        if(check(start)) System.out.println(start);
        else System.out.println(end);
//        check(5);

    }

    static boolean check(int k){
        boolean[] visited = new boolean[n];
        ArrayList<Integer>[] last_day = new ArrayList[k+1];
        for(int i=0;i<=k;i++){
            last_day[i] = new ArrayList<>();
        }
        for(int i=m-1;i>=0;i--){
            if(days[i].day>k){
                continue;
            }
            else {
                if(!visited[days[i].type]){
                    visited[days[i].type] = true;
                    last_day[days[i].day].add(days[i].type);
                }
            }
        }
//        print(last_day);
        int cost =0;
        int[] required = copies.clone();
        for(int i=1;i<=k;i++){
            if(last_day[i].size()==0){
                cost++;
            }
            else {
                cost++;
                for(int child:last_day[i]){
                    if(required[child]>0){
                        if(cost>=required[child]){
                            cost-=required[child];
                            required[child] =0;
                        }
                        else {
                            int temp = Math.min(cost,required[child]);
                            cost-=temp;
                            required[child]-=temp;
                        }
                    }
                }
            }

        }
        int total =0;
        for(int i=0;i<n;i++){
            total+=required[i];
        }
        if(cost>=2*total){
            return true;
        }
        return false;
    }

    static class pair implements  Comparable<pair>{
        int day;
        int type;
        pair(int day,int type) {
            this.day = day;
            this.type = type;
        }
        public int compareTo(pair p){
            return Integer.compare(this.day,p.day);
        }
    }







//    OutputStream out = new BufferedOutputStream( System.out );
//        for(int i=1;i<n;i++){
//              out.write((arr[i]+" ").getBytes());
//         }
//        out.flush();
//  long start_time = System.currentTimeMillis();
//  long end_time = System.currentTimeMillis();
//  System.out.println((end_time - start_time) + "ms");



}
