On Children's Day, the child got a toy from Delayyy as a present. However, the child is so naughty that he can't wait to destroy the toy.

The toy consists of n parts and m ropes. Each rope links two parts, but every pair of parts is linked by at most one rope. To split the toy, the child must remove all its parts. The child can remove a single part at a time, and each remove consume an energy. Let's define an energy value of part i as vi. The child spend vf1 + vf2 + ... + vfk energy for removing part i where f1, f2, ..., fk are the parts that are directly connected to the i-th and haven't been removed.

Help the child to find out, what is the minimum total energy he should spend to remove all n parts.

Input

The first line contains two integers n and m (1 ≤ n ≤ 1000; 0 ≤ m ≤ 2000). The second line contains n integers: v1, v2, ..., vn (0 ≤ vi ≤ 105). Then followed m lines, each line contains two integers xi and yi, representing a rope from part xi to part yi (1 ≤ xi, yi ≤ n; xi ≠ yi).

Consider all the parts are numbered from 1 to n.

Output

Output the minimum total energy the child should spend to remove all n parts of the toy.

Examples

Input

4 3
10 20 30 40
1 4
1 2
2 3


Output

40


Input

4 4
100 100 100 100
1 2
2 3
2 4
3 4


Output

400


Input

7 10
40 10 20 10 20 80 40
1 5
4 7
4 5
5 2
5 7
6 4
1 6
1 3
4 3
1 4


Output

160

Note

One of the optimal sequence of actions in the first sample is:

  * First, remove part 3, cost of the action is 20. 
  * Then, remove part 2, cost of the action is 10. 
  * Next, remove part 4, cost of the action is 10. 
  * At last, remove part 1, cost of the action is 0. 



So the total energy the child paid is 20 + 10 + 10 + 0 = 40, which is the minimum.

In the second sample, the child will spend 400 no matter in what order he will remove the parts.
import java.util.* ;
import java.io.* ;
import java.util.regex.* ;
import java.text.* ;
import java.math.* ;

public class Main {
	public static void main( String[] args ) {
		InputStream isObj ;
		OutputStream osObj ;
		InputReader irObj ;
		PrintWriter pwObj ;
		String inputFileName , outputFileName ;
		File fObj1 , fObj2 ;
		int T , ind ;
		boolean hasMoreInput , hasTestCases ;
		ProblemSolver psObj ;
		//only variable to be changed here is hasTestCases and osObj(optional for file output)
		hasTestCases = ProblemSolver.HAS_TEST_CASES ;
		isObj = System.in ;
		osObj = System.out ;
		inputFileName = ProblemSolver.INPUT_FILE_NAME ;
		outputFileName = ProblemSolver.OUTPUT_FILE_NAME ;
		try {
			fObj1 = new File( System.getProperty( "user.dir" ).toString() + "\\" + inputFileName ) ;
			fObj2 = new File( System.getProperty( "user.dir" ).toString() + "\\" + outputFileName ) ;
			if( fObj1.exists() == false ) {
				fObj1 = new File( System.getProperty( "user.dir" ).toString() + "\\src\\" + inputFileName ) ;
				fObj2 = new File( System.getProperty( "user.dir" ).toString() + "\\src\\" + outputFileName ) ;
			}
			isObj = new FileInputStream( fObj1 ) ;
			if( ProblemSolver.DO_OUTPUT_TO_FILE == true ) {
				osObj = new FileOutputStream( fObj2 ) ;
			}
		}
		catch( Exception ex ) {
			ex.printStackTrace() ;
			isObj = System.in ;
			osObj = System.out ;
		}
		irObj = new InputReader( isObj ) ;
		pwObj = new PrintWriter( osObj ) ;
		try {
			psObj = new ProblemSolver() ;
			if( hasTestCases == true ) {
				//for input with test cases
				T = irObj.nextInt() ;
				for( ind = 1 ; ind <= T ; ind++ ) {        	
					psObj.clearPerCase() ;
					psObj.getInput( irObj ) ;
					psObj.solveCase( pwObj ) ;
				}
			}
			else {
				//for end of file input
				for( ind = 1 ; ; ind++ ) {        	
					psObj.clearPerCase() ;
					hasMoreInput = psObj.getInput( irObj ) ;
					if( hasMoreInput == false ) {
						break ;
					}
					psObj.solveCase( pwObj ) ;
				}
			}
			pwObj.flush() ;
			isObj.close() ;
			osObj.close() ;
		}
		catch( Exception ex ) {
			ex.printStackTrace() ;
			throw new RuntimeException( ex ) ;
		}
		finally {
			pwObj.close() ;
		}
	}
}

class ProblemSolver {
	public static final boolean HAS_TEST_CASES = false ;
	public static final String INPUT_FILE_NAME = "test.in" ;
	public static final String OUTPUT_FILE_NAME = "out.txt" ;
	public static final boolean DO_OUTPUT_TO_FILE = false ;
	
	public void solveCase( PrintWriter pwObj ) {
		int i , j , a , b , c , sz , v , u , cnt , z , idx , de ;
		int res ;
		res = 0 ;
		z = 0 ;
		while( true ) {
			cnt = 0 ;
			for( i = 1 ; i <= this.n ; i++ ) {
				if( this.crr[ i ] == 1 ) {
					continue ;
				}
				sz = this.adj_list[ i ].size() ;
				a = 0 ;
				de = 0 ;
				for( j = 0 ; j < sz ; j++ ) {
					v = this.adj_list[ i ].get( j ) ;
					if( this.crr[ v ] == 1 ) {
						continue ;
					}
					a += this.arr[ v - 1 ] ;
					de++ ;
				}
				this.nrr[ cnt++ ] = new Node( i , a , this.arr[ i - 1 ] , de ) ; 
			}
			Arrays.sort( this.nrr , 0 , cnt ) ;
			/*
			for( i = 0 ; i < cnt ; i++ ) {
				pwObj.print( " " + this.nrr[ i ].getV() + "," + this.nrr[ i ].getF() + " " ) ;
			}
			pwObj.println( "" ) ;
			*/
			idx = 0 ;
			this.crr[ this.nrr[ idx ].getV() ] = 1 ;
			//pwObj.println( "...." + this.nrr[ idx ].getF() ) ;
			res += this.nrr[ idx ].getF() ;
			z++ ;
			if( z >= this.n ) {
				break ;
			}
		}
		pwObj.println( res ) ;
	}
	
	private void init() {
		//default values
		this.lim1 = 2010 ;
		this.lim2 = 110 ;
		this.cc = 1 ;
		this.ind = 0 ;
		this.declareArrays() ;
		this.fillAllArrays() ;
	}
	
	public boolean getInput( InputReader irObj ) {
		int i , u , v ;
		try {
			this.n = irObj.nextInt() ;
		}
		catch( Exception ex ) {
			return false ;
		}
		this.m = irObj.nextInt() ;
		for( i = 0 ; i < this.n ; i++ ) {
			this.arr[ i ] = irObj.nextInt() ;			
		}
		for( i = 0 ; i < this.m ; i++ ) {
			u = irObj.nextInt() ;
			v = irObj.nextInt() ;
			this.adj_list[ u ].add( v ) ;
			this.adj_list[ v ].add( u ) ;
		}
		return true ;
	}
	
	private int lim1 , lim2 , cn , ind , cc , n , m ; 
	private String[] srr ;
	private int[] arr , brr , crr ;
	private Node[] nrr ;
	private long[] lrr ;
	private int[][] memo , done ;
	private ArrayList< Integer >[] adj_list ;
	
	public void clearPerCase() {
		int i ;
		this.incrementInd() ;
		this.incrementCc() ;
		this.n = 0 ;
		this.cn = 0 ;
		Arrays.fill( this.crr , 0 ) ;
		for( i = 0 ; i < this.lim1 ; i++ ) {
			this.adj_list[ i ].clear() ;
		}
	}
	
	private void declareArrays() {
		//array declarations
		this.arr = new int[ this.lim1 ] ;
		this.brr = new int[ this.lim1 ] ;
		this.crr = new int[ this.lim1 ] ;
		this.lrr = new long[ this.lim1 ] ;
		this.srr = new String[ this.lim1 ] ;
		this.nrr = new Node[ this.lim1 ] ;
		this.memo = new int[ this.lim2 ][ this.lim2 ] ;
		this.done = new int[ this.lim2 ][ this.lim2 ] ;
		this.adj_list = new ArrayList[ this.lim1 ] ;
	}
	
	private void fillAllArrays() {
		int i ;
		//array initiations
		Arrays.fill( this.arr , 0 ) ;
		Arrays.fill( this.brr , 0 ) ;
		Arrays.fill( this.crr , 0 ) ;
		Arrays.fill( this.lrr , 0 ) ;
		for( int zrr[] : this.memo ) {
			Arrays.fill( zrr , -1 ) ;
		}
		for( int zrr[] : this.done ) {
			Arrays.fill( zrr , 0 ) ;
		}
		for( i = 0 ; i < this.lim1 ; i++ ) {
			this.srr[ i ] = new String( "" ) ;
			this.nrr[ i ] = new Node( Integer.MIN_VALUE , Integer.MIN_VALUE , Integer.MIN_VALUE , Integer.MIN_VALUE ) ;
			this.adj_list[ i ] = new ArrayList< Integer >() ;
		}
	}
	
	private void incrementInd() {
		this.ind++ ;
	}
	
	public void setCn( int c ) {
		this.cn = c ;  
	}
	
	public void incrementCn() {
		this.cn++ ;
	}
	
	public void incrementCc() {
		this.cc++ ;
	}
	
	public int getCn() {
		return this.cn ;
	}
	
	public ProblemSolver() {
		this.init() ;
	}
}

class Node implements Comparable< Node > {
	private int v , f , cur , deg ;
	
	private Node() {
	}
	
	public Node( int vParam , int fParam , int curParam , int degParam ) {
		this.v = vParam ;
		this.f = fParam ;
		this.cur = curParam ;
		this.deg = degParam ;
	}
	
	public void setV( int vParam ) {
		this.v = vParam ;
	}
	
	public void setF( int fParam ) {
		this.f = fParam ;
	}
	
	public void setCur( int curParam ) {
		this.cur = curParam ;
	}
	
	public void setDeg( int degParam ) {
		this.deg = degParam ;
	}
	
	public int getV() {
		return this.v ;
	}
	
	public int getF() {
		return this.f ;
	}
	
	public int getCur() {
		return this.cur ;
	}
	
	public int getDeg() {
		return this.deg ;
	}
	
	public int compareTo( Node nParam ) {
		if( nParam.getCur() == this.getCur() ) {
			return nParam.getDeg() - this.getDeg() ;
		}
		return nParam.getCur() - this.getCur() ;
		
	}
}

class InputReader {
	private BufferedReader reader ;
	private StringTokenizer tokenizer ;

	public InputReader( InputStream stream ) {
		this.reader = new BufferedReader( new InputStreamReader( stream ) ) ;
		this.tokenizer = null ;
	}

	private String next( int fl ) {
		while( this.tokenizer == null || ! this.tokenizer.hasMoreTokens() ) {
			try {                
				this.tokenizer = new StringTokenizer( this.reader.readLine() ) ;
			}
			catch( IOException e ) {
				throw new RuntimeException( e ) ;
			}
		}
		String s ;
		s = "" ;
		if( fl == 1 ) {
			s = this.tokenizer.nextToken() ; 
		}
		return s ;
	}

	public String nextLine() {
		this.next( 0 ) ;
		int fl ;
		String line ;
		line = "" ;
		fl = 0 ;
		if( this.tokenizer != null ) {
			while( this.tokenizer.hasMoreTokens() ) {
				if( fl == 1 ) {
					line += " " ;
				}
				fl = 1 ;
				line += this.tokenizer.nextToken() ;
			}
		}
		return line ;
	}

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

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

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

	public String nextString() {
		return this.next( 1 ) ;
	}
}