//n件物品，m种关系，(有关系的2个不能在同一组)

 //把所有物品分为2组，希望最后2组的差值尽可能小，输出较大者

 /*

 二分图涂色+可行性(01)背包

 dp[i]  =1表示 最后差值为i可行

 建图后，对于每个连通分量记录差值,来求所有的可行

 */

 #include<bits/stdc++.h>

 using namespace std;

 int  t,n,m;

 #define N 250

 #define M 102000

 int a[N],head[N],sum;

 int cnt,vis[N];

 int dp[M],dp1[M];

 int     sum1=,sum2=;

 void init(){

     cnt  = ;

     for(int i =;i<N;i++) {

         head[i] = -;

         vis[i]  =;//多组输入

     }

 }

 struct Node{

     int u,v,nex;

 }e[N*];

 void add(int u,int  v)

 {

     e[cnt].u=u;e[cnt].v=v;

     e[cnt].nex=head[u];head[u]=cnt++;

 }

 void dfs(int x,int rt){

     vis[x] = ;

     if(rt==)

     sum1+=a[x];

     else{

         sum2+=a[x];

     }

     for(int i =head[x];i!=-;i=e[i].nex){

         int v = e[i].v;

         if(!vis[v])

         dfs(v,rt^);//0^1=1,1^1=0

     }

 }

 int main()

 {

     scanf("%d",&t);

     while(t--)

     {

         init();

         scanf("%d%d",&n,&m);

         int x,y;

         sum =;

         for(int i =;i<=n;i++)

         {

             scanf("%d",&a[i]);

             sum+=a[i]/;

             a[i]/=;//题目说明都是100的倍数

         }

         for(int i =;i<m;i++) {

             scanf("%d%d",&x,&y);

             add(x,y);add(y,x);//无向图

         }

         int num;

         for(int i =;i<=sum;i++) dp[i] = ;

         dp[] = ;//dp[0]一定先设为1，来引入第一个差值

         for(int i =;i<=n;i++) {

             if(!vis[i]){

                 sum1=,sum2=;

                 dfs(i,);

                 num = abs(sum1-sum2);

                 //printf("%d %d %d\n",sum1,sum2,num);

                 for(int j=sum;j>=;j--){

                     if(dp[j]){

                         //如 ：0，j. 0 ,num 或者 j,0.0,num

                         if(abs(j+num)<=sum) dp1[abs(j+num)] =;

                         dp1[abs(j-num)]  =;

                     }

                 }

                 for(int j =sum;j>=;j--){

                     dp[j]  = dp1[j],dp1[j] = ;

                 }

             }

         }

         //一定需要2个dp 数组，利用dp1一直更新到所有的物品都取完

         for(int i =;i<=sum;i++) {

             if(dp[i]){

                 printf("%d\n",(sum+i)/*);

                 break;

             }

         }

     }

     return ;

 }