//#include <bits/stdc++.h>

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #define t_mid (l+r>>1)

 #define ls (o<<1)

 #define rs (o<<1|1)

 #define lson ls,l,t_mid

 #define rson rs,t_mid+1,r

 using namespace std;

 const int N =  + ;

 int a[N];

 // sub表示节点o的lcis的最长长度，l_val和r_val分别表示这个节点最左边和最右边的值分别是多少

 // l_sub表示这个节点从最左边开始的最长的lcis的长度，r_sub同

 int sub[N<<],l_val[N<<],r_val[N<<],l_sub[N<<],r_sub[N<<];

 int T,n,q;

 void up(int o,int l,int r)

 {

     int len = r - l + ;

     l_val[o] = l_val[ls], r_val[o] = r_val[rs]; // 更新l_val,r_val

     // 更新sub的值

     sub[o] = max(sub[ls], sub[rs]);

     if(r_val[ls] < l_val[rs]) sub[o] = max(sub[o], r_sub[ls]+l_sub[rs]);

     // 更新l_sub,r_sub

     l_sub[o] = l_sub[ls];

     if(l_sub[o] == len-len/ && r_val[ls] < l_val[rs]) l_sub[o] += l_sub[rs];

     r_sub[o] = r_sub[rs];

     if(r_sub[o] == len/ && r_val[ls] < l_val[rs]) r_sub[o] += r_sub[ls];

 }

 void build(int o,int l,int r)

 {

     if(l == r)

     {

         sub[o] = l_sub[o] = r_sub[o] = ;

         l_val[o] = r_val[o] = a[l];

         return ;

     }

     build(lson);

     build(rson);

     up(o,l,r);

 }

 void update(int o,int l,int r,int pos,int x)

 {

     if(l == r)

     {

         l_val[o] = r_val[o] = x;

         return ;

     }

     if(pos <= t_mid) update(lson,pos,x);

     else update(rson,pos,x);

     up(o,l,r);

 }

 int query(int o,int l,int r,int ql,int qr)

 {

     if(l == ql && r == qr) return sub[o];

     int ans = ;

     if(qr <= t_mid) ans = query(lson,ql,qr);

     else if(ql > t_mid) ans = query(rson,ql,qr);

     else

     {

         ans = max(query(lson,ql,t_mid), query(rson,t_mid+,qr));

         // 注意下面一行的两个min

         if(r_val[ls] < l_val[rs]) ans = max(ans, min(r_sub[ls], t_mid-ql+) + min(l_sub[rs], qr-t_mid));

     }

     return ans;

 }

 int main()

 {

     scanf("%d",&T);

     while(T--)

     {

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

         for(int i=;i<=n;i++) scanf("%d",a+i);

         build(,,n);

         while(q--)

         {

             char s[];

             int x,y;

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

             if(s[] == 'U') update(,,n,x+,y);

             else printf("%d\n",query(,,n,x+,y+));

         }

     }

     return ;

 }

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <iostream>

 #include <stdlib.h>

 #include <string>

 #include <stack>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 typedef long long ll;

 typedef pair<int,int> pii;

 const int N =  + ;

 int n,m,k;

 vector<pii> v[];

 int dp[][+];

 int main()

 {

     while(scanf("%d%d%d",&n,&m,&k) == )

     {

         for(int i=;i<=k;i++) v[i].clear();

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

         {

             int pos,mo,val;

             scanf("%d%d%d",&pos,&mo,&val);

             v[pos].push_back(pii(mo,val));

         }

         int sum = ;

         int flag = ;

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

         {

             if(v[i].size() == )

             {

                 flag = ;

                 break;

             }

             sort(v[i].begin(), v[i].end());

             sum += v[i][].first;

         }

         if(sum > m || flag == )

         {

             printf("Impossible\n");

             continue;

         }

         memset(dp,,sizeof dp);

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

         {

             for(int j=;j<v[i].size();j++)

             {

                 int w = v[i][j].first, val = v[i][j].second;

                 for(int mask=m;mask>=w;mask--)

                 {

                     if(j == ) dp[i][mask] = dp[i-][mask-w] + val;

                     else dp[i][mask] = max({dp[i][mask], dp[i-][mask-w]+val, dp[i][mask-w]+val});

                 }

             }

         }

         printf("%d\n",dp[k][m]);

     }

 }