Problem: The only difference between easy and hard versions is a number of elements in the array.

You are given an array a consisting of n integers. The value of the i-th element of the array is a_i.

You are also given a set of m segments. The j-th segment is [l_j; r_j], where 1 ≤ l_j ≤ r_j ≤ n.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a = [0, 0, 0, 0, 0] and the given segments are [1; 3] and [2; 4] then you can choose both of them and the array will become b = [-1, -2, -2, -1, 0].

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array a and obtain the array b then the value max_{i=1}^{n}b_i - min_{i=1}^{n}b_i will be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 300, 0 ≤ m ≤ 300) — the length of the array a and the number of segments, respectively.

The second line of the input contains n integers a_1, a_2, ..., a_n (-10^6 ≤ a_i ≤ 10^6), where a_i is the value of the i-th element of the array a.

The next m lines are contain two integers each. The j-th of them contains two integers l_j and r_j (1 ≤ l_j ≤ r_j ≤ n), where l_j and r_j are the ends of the j-th segment.

Output

In the first line of the output print one integer d — the maximum possible value max_{i=1}^{n}b_i - min_{i=1}^{n}b_i if b is the array obtained by applying some subset of the given segments to the array a.

In the second line of the output print one integer q (0 ≤ q ≤ m) — the number of segments you apply.

In the third line print q distinct integers c_1, c_2, ..., c_q in any order (1 ≤ c_k ≤ m) — indices of segments you apply to the array a in such a way that the value max_{i=1}^{n}b_i - min_{i=1}^{n}b_i of the obtained array b is maximum possible.

If there are multiple answers, you can print any.

Examples

Input


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


Output


6
2
1 4 


Input


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


Output


7
2
3 2 


Input


1 0
1000000


Output


0
0

Note

In the first example the obtained array b will be [0, -4, 1, 1, 2] so the answer is 6.

In the second example the obtained array b will be [2, -3, 1, -1, 4] so the answer is 7.

In the third example you cannot do anything so the answer is 0.

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		InputReader in = new InputReader(inputStream);
//		InputStream uinputStream = new FileInputStream("crowded.in");
//		InputReader in = new InputReader(uinputStream);
//		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("crowded.out")));
		Task t = new Task();
		t.solve(in, out);
		out.close();
	}
	
	static class Task {		
		
		public void solve(InputReader in, PrintWriter out) throws IOException {
			//Dumper.print(Long.MAX_VALUE);
//			int n = in.nextInt();
//			int q = in.nextInt();
//			a = new int[n];
//			for(int i=0;i<n;i++) a[i] = in.nextInt();
//			SegTree st = new SegTree(0,n);
//			for(int i=0;i<q;i++) {
//				int f = in.nextInt();
//				int t = in.nextInt();
//				//Dumper.print(st.queryMax(f-1, t));
//				//Dumper.print(st.queryMin(f-1, t));
//				out.println(a[st.queryMax(f-1, t)]-a[st.queryMin(f-1, t)]);
//			}
			
//			int n = in.nextInt();	
//			int[][] arr = new int[n][2];
//			for(int i=0;i<n;i++) {
//				arr[i][1] = in.nextInt();
//				arr[i][0] = in.nextInt();
//			}
//			Arrays.sort(arr, (a,b)->(a[0]-b[0]));
//			TreeMap<Integer, Integer> pos = new TreeMap<Integer, Integer>();
//			for(int i=0;i<n;i++) pos.put(arr[i][0], i);
//			int left_cover[] = new int[n];
//			boolean left_done[] = new boolean[n];
//			Arrays.fill(left_done, true);
//			for(int i=0;i<n-1;i++) {
//				left_cover[i] = pos.floorKey(arr[i][0]+arr[i][1]);
//				if(left_cover[i]==i) left_done[i] = false;
//				if(i>0) left_done[i]&=left_done[i-1];
//			}
//			int right_cover[] = new int[n];
//			boolean right_done[] = new boolean[n];
//			Arrays.fill(right_done, true);
//			for(int i=n-1;i>0;i--) {
//				right_cover[i] = pos.ceilingKey(arr[i][0]-arr[i][1]);
//				if(left_cover[i]==i) right_done[i] = false;
//				if(i>0) right_done[i]&=right_done[i-1];
//			}
//			Dumper.print("here");
			
//			int n = in.nextInt();
//			int e = in.nextInt();			
//			int MAX = 99999999;
//			int tmp[][] = new int[n+1][n+1];
//			int dist[][] = new int[n+1][n+1];
//			int w[][] = new int[n+1][2];
//			ArrayList<Integer> g[] = new ArrayList[n+1];
//			for(int i=1;i<=n;i++) g[i] = new ArrayList<Integer>();
//			
//			
//			for(int i=1;i<=n;i++) {
//				Arrays.fill(tmp[i], MAX);
//				Arrays.fill(dist[i], MAX);
//				tmp[i][i] = 0;
//				dist[i][i] = 0;
//			}
//			for(int i=1;i<=n;i++) {
//				int v = in.nextInt();
//				int num = in.nextInt();
//				w[i][0] = v;
//				w[i][1] = i;
//				for(int j=0;j<num;j++) {
//					int u = in.nextInt();
//					tmp[i][u] = 1;
//				}				
//			}
//			Arrays.sort(w, (a,b)->(a[0]-b[0]));
//			int[] hash = new int[n+2];
//			Arrays.fill(hash, -1);
//			for(int i=1;i<=n;i++) {
//				hash[w[i][1]] = i;
//			}
//			
//			for(int i=1;i<=n;i++) {
//				for(int j=1;j<=n;j++) {
//					if(tmp[i][j]==1) {
//						dist[hash[i]][hash[j]] = tmp[i][j];
//						g[hash[i]].add(hash[j]);
//					}
//				}
//			}
//			
//			int f[][] = new int[n+1][21];
//			int dep[] = new int[n+1];
//			
//				
//			for(int k=0;k<n;k++) {
//				for(int i=0;i<n;i++) {
//					for(int j=0;j<n;j++) {
//						dist[i][j] = Math.min(dist[i][k]+dist[k][j], dist[i][j]);
//					}
//				}
//			}
//			
//			long max = -1;
//			for(int i=0;i<n;i++) {
//				int weg = w[i][0];
//				int dp[] = new int[n];
//				Arrays.fill(dp, -1);
//				dp[i] = weg;
//				for(int j=i+1;j<n;j++) {
//					for(int k=i;k<j;k++) {
//						if(dp[k]>=0&&dist[w[j][1]][w[k][1]]!=MAX)
//							dp[j] = Math.max(dp[j], dp[k]+w[j][0]-dist[w[j][1]][w[k][1]]*e);
//						if(dp[j]>max) max = dp[j];
//					}
//				}
//			}
//			out.println(max);
//			Dumper.print(max);
			
//			int n = in.nextInt();
//			int d = in.nextInt();
//			TreeMap<Integer,Integer> ts = new TreeMap<Integer,Integer>();
//			int arr[][] = new int[n][2];
//			for(int i=0;i<n;i++) {
//				arr[i][0] = in.nextInt();
//				arr[i][1] = in.nextInt();				
//			}
//			Arrays.sort(arr, (a,b)->(a[0]-b[0]));
//			for(int i=0;i<n;i++) ts.put(arr[i][0], i);
//			
//			int st[][] = new int[n][20];
//			for(int i=0;i<n;i++) st[i][0] = arr[i][1];
//			for(int k=1;k<20;k++) {
//				for(int i=0;i+(1<<k)-1<n;i++) {
//					st[i][k] = Math.max(st[i][k-1], st[i+(1<<k-1)][k-1]);
//				}
//			}
//			int log[] = new int[n+1];
//			log[0] = -1;
//			for(int i=1;i<=n;i++) log[i] = log[i>>1]+1;
//			
//			int ret = 0;
//			for(int i=1;i<n-1;i++){
//				int h = arr[i][1];
//				Integer l = ts.get(ts.ceilingKey(arr[i][0]-d));
//				Integer r = ts.get(ts.floorKey(arr[i][0]+d));
//				if(l==null||r==null) continue;				
//				int c = log[i-l+1];
//				int left = Math.max(st[l][c], st[i-(1<<c)+1][c]);
//				c = log[r-i+1];
//				int right = Math.max(st[i][c], st[r-(1<<c)+1][c]);
//				int max = Math.min(left, right);
//				//Dumper.print(i+" "+r+" "+l+" "+h+" "+max);
//				if(max>=2*h) ret++;
//			}
//			Dumper.print(ret);
//			out.println(ret);
			int n = in.nextInt();
			int m = in.nextInt();
			int arr[] = new int[n];
			for(int i=0;i<n;i++) arr[i] = in.nextInt();
			int seg[][] = new int[m][2];
			for(int i=0;i<m;i++) {
				seg[i][0] = in.nextInt()-1;
				seg[i][1] = in.nextInt()-1;
			}
			ArrayList<Integer> ret = new ArrayList<Integer>();
			int max = 0;
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(i==j) continue;
					ArrayList<Integer> tmp = new ArrayList<Integer>();					
					int a = arr[i]; int b = arr[j];
					for(int k=0;k<m;k++) {
						if(i>=seg[k][0]&&i<=seg[k][1]) {
							if(j<seg[k][0]||j>seg[k][1]) {
								a--;
								tmp.add(k);
							}
						}
					}
					if(b-a>max) {
						max = b-a;
						ret = new ArrayList<Integer>(tmp);
					}
				}
			}
			out.println(max);
			out.println(ret.size());
			for(int i=0;i<ret.size();i++) {
				if(i!=0) out.print(" ");
				out.print(ret.get(i)+1);
			}
			out.println();
		}

	    public int[] movesToStamp(String stamp, String target) {
	    	int n = stamp.length();
	    	int m = target.length();
	    	char[] s = stamp.toCharArray();
	    	char[] t = target.toCharArray();
	    	ArrayList<Integer> part1 = new ArrayList<Integer>();
	    	ArrayList<Integer> part2 = new ArrayList<Integer>();
	    	ArrayList<Integer> part3 = new ArrayList<Integer>();
	    	int p = target.indexOf(stamp);
            if(p==-1) return new int[] {};
            part1.add(p);
	    	update(t,p,p+stamp.length());
	    	while(true) {
	    		int x = target.indexOf(stamp,p+stamp.length());	    		
	    		if(x==-1) break;
	    		update(t,x,x+stamp.length());
	    		part1.add(0,x);
	    		p=x;
	    	}	    
	    	
	    	TreeSet<Integer> todo = new TreeSet<Integer>(Collections.reverseOrder());
	    	for(int i=0;i<m;i++) if(t[i]!='*') todo.add(i);
	    	
	    	while(true) {
	    		int temp = -1;
	    		for(int i:todo) {
	    			if(i+1<m&&t[i+1]=='*') {
	    				temp = i;
	    				int tmp = stamp.indexOf(t[i]);
	    				if(i-tmp<0) return new int[] {};
	    				part2.add(i-tmp);	    			
	    				t[i]='*';
	    				break;
	    			}
	    		}
	    		if(temp==-1) break;
	    		else todo.remove(temp);
	    	}
	    	
	    	while(!todo.isEmpty()) {
	    		int l = 0; int end = 0;
	    		for(int i:todo) {
	    			end=i;
	    			l = backmatch(s,t,i);
	    			part3.add(i-n+1);	    			
	    			update(t,i-l+1,i);
	    			break;
	    		}
	    		if(l==0) return new int[] {};
	    		else {
	    			for(int j=end-l+1;j<=end;j++)
	    				todo.remove(j);    		
	    		}
	    	}	    	
	    	int[] ret = new int[part1.size()+part2.size()+part3.size()];	
	    	int c=0;
	    	for(int i:part3) {
	    		ret[c++] = i;
	    	}
	    	for(int i:part2) {
	    		ret[c++] = i;
	    	}
	    	for(int i:part1) {
	    		ret[c++] = i;
	    	}	    	
	    	return ret;
	    }
	    public int backmatch(char s[], char t[], int idx) {
	    	int q = s.length-1;
	    	int c = 0;
	    	while(q>0&&idx>0&&s[q]==t[idx]) {
	    		q--;idx--;c++;
	    	}
	    	return c;
	    }
	    public void update(char[] arr, int s, int l) {
	    	for(int i=s;i<l;i++) arr[i] = '*';
	    }
	}
	
	class BIT{
		int arr[];
		int n;
		public BIT(int a) {
			n=a;
			arr = new int[n];
		}
		int sum(int p) {
			int s=0;
			while(p>0) {
				s+=arr[p];
				p-=p&(-p);
			}
			return s;
		}
		void add(int p, int v) {
			while(p<n) {
				arr[p]+=v;
				p+=p&(-p);
			}
		}
	}
	static class DSU{
		int[] arr;
		int[] sz;
		public DSU(int n) {
			arr = new int[n];
			sz = new int[n];
			for(int i=0;i<n;i++) arr[i] = i;
			Arrays.fill(sz, 1);
		}
		public int find(int a) {
			if(arr[a]!=a) arr[a] = find(arr[a]);
			return arr[a];
		}
		public void union(int a, int b) {
			int x = find(a);
			int y = find(b);
			if(x==y) return;
			arr[x] = y;
			sz[y] += sz[x];
		}
		public int size(int x) {
			return sz[find(x)];
		}
	}	
	static class MinHeap<Key> implements Iterable<Key> {
		private int maxN;
		private int n;
		private int[] pq;
		private int[] qp;
		private Key[] keys;
		private Comparator<Key> comparator;
		
		public MinHeap(int capacity){
			if (capacity < 0) throw new IllegalArgumentException();
			this.maxN = capacity;
			n=0;
			pq = new int[maxN+1];
			qp = new int[maxN+1];
			keys = (Key[]) new Object[capacity+1];
			Arrays.fill(qp, -1);
		}
		
		public MinHeap(int capacity, Comparator<Key> c){
			if (capacity < 0) throw new IllegalArgumentException();
			this.maxN = capacity;
			n=0;
			pq = new int[maxN+1];
			qp = new int[maxN+1];
			keys = (Key[]) new Object[capacity+1];
			Arrays.fill(qp, -1);
			comparator = c;
		}			
		public boolean isEmpty()	{ return n==0; 	}
		public int size()			{ return n;		}
		public boolean contains(int i) {
	        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
	        return qp[i] != -1;
		}	
		public int peekIdx() {
	        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
	        return pq[1];		
		}	
		public Key peek(){
			if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
			return keys[pq[1]];
		}
		public int poll(){
			if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
			int min = pq[1];
			exch(1,n--);
			down(1);
			assert min==pq[n+1];
			qp[min] = -1;
			keys[min] = null;		
			pq[n+1] = -1;
			return min;
		}
	    public void update(int i, Key key) {
	        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
	        if (!contains(i)) {
	        	this.add(i, key);
	        }else {
	        	keys[i] = key;
	        	up(qp[i]);
	        	down(qp[i]);
	        }
	    }	
		private void add(int i, Key x){
	        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
	        if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
	        n++;
	        qp[i] = n;
	        pq[n] = i;
	        keys[i] = x;
	        up(n);
		}
		private void up(int k){
			while(k>1&&less(k,k/2)){
				exch(k,k/2);
				k/=2;
			}
		}
		private void down(int k){
			while(2*k<=n){
				int j=2*k;
				if(j<n&&less(j+1,j)) j++;
				if(less(k,j)) break;
				exch(k,j);
				k=j;
			}
		}
		
		public boolean less(int i, int j){
	        if (comparator == null) {
	            return ((Comparable<Key>) keys[pq[i]]).compareTo(keys[pq[j]]) < 0;
	        }
	        else {
	            return comparator.compare(keys[pq[i]], keys[pq[j]]) < 0;
	        }
		}

		public void exch(int i, int j){
	        int swap = pq[i];
	        pq[i] = pq[j];
	        pq[j] = swap;
	        qp[pq[i]] = i;
	        qp[pq[j]] = j;
		}

		@Override
		public Iterator<Key> iterator() {
			// TODO Auto-generated method stub
			return null;
		}
	}  	

    private static class InputReader
    {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int zcurChar;
        private int znumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream)
        {
            this.stream = stream;
        }

        public int read()
        {
            if (znumChars == -1)
                throw new InputMismatchException();
            if (zcurChar >= znumChars)
            {
            	zcurChar = 0;
                try
                {
                    znumChars = stream.read(buf);
                } catch (IOException e)
                {
                    throw new InputMismatchException();
                }
                if (znumChars <= 0)
                    return -1;
            }
            return buf[zcurChar++];
        }

        public int nextInt()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String nextString()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do
            {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public double nextDouble()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.')
            {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.')
            {
                c = read();
                double m = 1;
                while (!isSpaceChar(c))
                {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public long nextLong()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c)
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next()
        {
            return nextString();
        }

        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }    

	static class Dumper {
		static void print_int_arr(int[] arr) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_char_arr(char[] arr) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_double_arr(double[] arr) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_2d_arr(int[][] arr, int x, int y) {
			for (int i = 0; i < x; i++) {
				for (int j = 0; j < y; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_2d_arr(boolean[][] arr, int x, int y) {
			for (int i = 0; i < x; i++) {
				for (int j = 0; j < y; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print(Object o) {
			System.out.println(o.toString());
		}

		static void getc() {
			System.out.println("here");
		}
	}
}