#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include<set>
#include<algorithm>
#include <iostream>
#include <cassert>
#include <cstdio>
void init(int N, int Q, std::vector<int> X, std::vector<int> Y);
int max_prize(int L, int R);
using namespace std;
#define SUBMIT 1
#ifndef SUBMIT
int main() {
int N, Q;
assert(scanf("%d %d", &N, &Q) == 2);
std::vector<int> X(N), Y(N);
for (int i = 0; i < N; i++) { assert(scanf("%d", &X[i]) == 1); }
for (int i = 0; i < N; i++) { assert(scanf("%d", &Y[i]) == 1); }
init(N, Q, X, Y);
for (int k = 0; k < Q; k++) {
int L, R;
assert(scanf("%d %d", &L, &R) == 2);
printf("%d\n", max_prize(L, R));
fflush(stdout);
}
}
#endif
vector<pair<int, int>> arr;
bool f = 0;
struct comp {
bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
if (a == b)return 0;
if ((a.first - a.second) == (b.first - b.second))
return (f?(a.first>b.first):(a.second<b.second));
return (a.first - a.second) > (b.first - b.second);
}
};
void init(int n, int q, vector<int> x, vector<int> y) {
for (int i = 0; i < n; ++i)
arr.push_back({ x[i], y[i] });
}
int max_prize(int l, int r) {
int s1 = 0, s2 = 0;
for (int i = l; i <= r; ++i)
s1 += arr[i].first, s2 += arr[i].second;
if (s1 > s2) f = 0; else f = 1;
multiset<pair<int, int>, comp> a;
for (int i = l; i <= r; ++i) a.insert(arr[i]);
int n = a.size(), ans = 0;
while (1) {
int cnt = 0;
bool ok = 1;
auto s = a;
for (auto x : a) {
s.erase(s.find(x));
if (cnt < (n / 2)) { //make red
if (x.first == 0) { ok = 0; break; }
s.insert({ x.first - 1, x.second });
}
else { //make blue
if (x.second == 0) { ok = 0; break; }
s.insert({ x.first, x.second - 1 });
}
++cnt;
}
if (!ok) break;
++ans, a = s;
}
return ans;
}
