#include "bits/stdc++.h"
using namespace std;
const int N = 505;
int t;
int n;
int arr[N];
bitset < N * N > bit;
int solve(vector < int > &v){
int sum = 0;
for(int x : v){
sum += x;
}
bit.reset();
bit.set(0);
for(int x : v){
bit |= (bit << x);
}
int ans = sum;
for(int i = 0 ; i < sum ; ++i){
if(bit.test(i)){
ans = min(ans , abs(i - (sum - i)));
}
}
return ans;
}
int main(){
scanf("%d" , &t);
while(t--){
scanf("%d" , &n);
char ty[3];
for(int i = 0 ; i < n ; ++i){
scanf("%d %s" , arr + i , ty);
}
scanf("%d" , &arr[n]);
if(n <= 2){
printf("NO\n");
continue;
}
vector < int > v1;
vector < int > v2;
v1.clear();
v2.clear();
for(int i = 0 ; i <= n ; i += 2){
v1.emplace_back(arr[i]);
}
for(int i = 1 ; i <= n ; i += 2){
v2.emplace_back(arr[i]);
}
printf("%d\n" , solve(v1) + solve(v2));
}
}
I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBOID0gNTA1OwppbnQgdDsKaW50IG47CmludCBhcnJbTl07CmJpdHNldCA8IE4gKiBOID4gYml0OwppbnQgc29sdmUodmVjdG9yIDwgaW50ID4gJnYpewoJaW50IHN1bSA9IDA7Cglmb3IoaW50IHggOiB2KXsKCQlzdW0gKz0geDsKCX0KCWJpdC5yZXNldCgpOwoJYml0LnNldCgwKTsKCWZvcihpbnQgeCA6IHYpewoJCWJpdCB8PSAoYml0IDw8IHgpOwoJfQoJaW50IGFucyA9IHN1bTsKCWZvcihpbnQgaSA9IDAgOyBpIDwgc3VtIDsgKytpKXsKCQlpZihiaXQudGVzdChpKSl7CgkJCWFucyA9IG1pbihhbnMgLCBhYnMoaSAtIChzdW0gLSBpKSkpOwoJCX0KCX0KCXJldHVybiBhbnM7Cn0KaW50IG1haW4oKXsKCXNjYW5mKCIlZCIgLCAmdCk7Cgl3aGlsZSh0LS0pewoJCXNjYW5mKCIlZCIgLCAmbik7CgkJY2hhciB0eVszXTsKCQlmb3IoaW50IGkgPSAwIDsgaSA8IG4gOyArK2kpewoJCQlzY2FuZigiJWQgJXMiICwgYXJyICsgaSAsIHR5KTsKCQl9CgkJc2NhbmYoIiVkIiAsICZhcnJbbl0pOwoJCWlmKG4gPD0gMil7CgkJCXByaW50ZigiTk9cbiIpOwoJCQljb250aW51ZTsKCQl9CgkJdmVjdG9yIDwgaW50ID4gdjE7CgkJdmVjdG9yIDwgaW50ID4gdjI7CgkJdjEuY2xlYXIoKTsKCQl2Mi5jbGVhcigpOwoJCWZvcihpbnQgaSA9IDAgOyBpIDw9IG4gOyBpICs9IDIpewoJCQl2MS5lbXBsYWNlX2JhY2soYXJyW2ldKTsKCQl9CgkJZm9yKGludCBpID0gMSA7IGkgPD0gbiA7IGkgKz0gMil7CgkJCXYyLmVtcGxhY2VfYmFjayhhcnJbaV0pOwoJCX0KCQlwcmludGYoIiVkXG4iICwgc29sdmUodjEpICsgc29sdmUodjIpKTsKCX0KfSA=
Q29kZUNoZWYgc3VibWlzc2lvbiAxMDU0OTk5MSAoQysrMTQpIHBsYWludGV4dCBsaXN0LiBTdGF0dXM6IEFDLCBwcm9ibGVtIFJXQUxLLCBjb250ZXN0IFNOQ0tFTDE2LiBCeSB3aW5fc25hY2tkb3duICh3aW5fc25hY2tkb3duKSwgMjAxNi0wNi0xOSAyMTo0OTozNC4=
CodeChef submission 10549991 (C++14) plaintext list. Status: AC, problem RWALK, contest SNCKEL16. By win_snackdown (win_snackdown), 2016-06-19 21:49:34.