#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    int ans = a[n - 1];
    for (int i = 0; i < n - 1; ++i)
      ans += max(0, a[i] - b[i + 1]);
    cout << ans << '\n';
  }
}

t = int(input())
for i in range(t):
    n, a, b, c = map(int, input().split())
    sum = a + b + c
    d = n // sum * 3
    if n % sum == 0:
        print(d)
    elif n % sum <= a:
        print(d + 1)
    elif n % sum <= a + b:
        print(d + 2)
    else:
        print(d + 3)

for _ in range(int(input())):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    q = list(map(int, input().split()))
    used = [False for i in range(n + 1)]
    for i in q:
        used[i] = True
    l = len(q)
    for i in range(m):
        if l == n or (l == n-1 and not used[a[i]]):
            print(1, end='')
        else:
            print(0, end='')
    print()

def calcLessThanX(a, x):
    n = len(a)
    s = sum(a)
    j = 0
    ans = 0

    for i in range(n-1, -1, -1):
        while j < n and s - a[i] - a[j] >= x:
            j += 1
        ans += (n - j)

    for i in range(n):
        if s - a[i] - a[i] < x:
            ans -= 1
    
    return ans // 2

for _ in range(int(input())):
    n, x, y = map(int, input().split())
    a = list(map(int, input().split()))
    
    a = sorted(a)
    print(calcLessThanX(a, y+1) - calcLessThanX(a, x))

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    vector<pair<int, int>> ev;
    for (int i = 0; i < n; ++i) {
      ev.emplace_back(a[i], 1);
      ev.emplace_back(b[i], 2);
    }
    sort(ev.begin(), ev.end());
    long long ans = 0;
    int cnt = n, bad = 0;
    for (int i = 0; i < 2 * n;) {
      auto [x, y] = ev[i];
      if (bad <= k) ans = max(ans, x * 1LL * cnt);
      while (i < 2 * n && ev[i].first == x) {
        bad += (ev[i].second == 1);
        bad -= (ev[i].second == 2);
        cnt -= (ev[i].second == 2);
        ++i;
      }
    }
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> segs({{1, -q}, {m, m}, {n + q + 1, n}});
    while (q--) {
      int x;
      cin >> x;
      bool ins = false;
      for (auto& [l, r] : segs) {
        if (x < l) l = max(1, l - 1);
        else if (x > r) r = min(n, r + 1);
        else {
          ins = true;
          if (l == r) l = n + q, r = -q;
        }
      }
      if (ins) {
        segs[0] = {1, max(segs[0].second, 1)};
        segs[2] = {min(segs[2].first, n), n};
      }
      int lf = 0, rg = -1, ans = 0;
      for (auto [l, r] : segs) {
        if (l > r) continue;
        if (l > rg) {
          ans += max(0, rg - lf + 1);
          lf = l; rg = r;
        }
        rg = max(rg, r);
      }
      ans += max(0, rg - lf + 1);
      cout << ans << ' ';
     }
     cout << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

const int INF = int(1e9);

int n, q;
vector<int> id, ch;

bool read() {
    if (!(cin >> n >> q))
        return false;
    id.resize(q);
    ch.resize(q);
    fore (i, 0, q) {
        char c;
        cin >> id[i] >> c;
        id[i]--;
        ch[i] = c == '+' ? 1 : -1;
    }
    return true;
}

int getDist(int s, int t) {
    int pSum = 0, cMin = 0;
    fore (e, 0, q) {
        if (id[e] == t)
            pSum += ch[e] < 0;
        if (id[e] == s)
            pSum -= ch[e] > 0;
        cMin = min(cMin, pSum);
    }
    return -cMin + 1;
}

inline void solve() {
    vector<vector<int>> minDist(n, vector<int>(n, INF));

    fore (i, 0, n) fore (j, 0, n)
        minDist[i][j] = getDist(i, j);

    vector<int> len(n, 0);
    fore (e, 0, q)
        len[id[e]] += ch[e] > 0;
    
    vector< vector<int> > d(1 << n, vector<int>(n, INF));
    fore (i, 0, n)
        d[1 << i][i] = 1;
    
    fore (mask, 1, 1 << n) fore (lst, 0, n) {
        if (d[mask][lst] == INF)
            continue;
        fore (nxt, 0, n) {
            if ((mask >> nxt) & 1)
                continue;
            int nmask = mask | (1 << nxt);
            d[nmask][nxt] = min(d[nmask][nxt], d[mask][lst] + minDist[lst][nxt]);
        }
    }
    int ans = INF;
    fore (lst, 0, n)
        ans = min(ans, d[(1 << n) - 1][lst] + len[lst]);
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);

    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}