#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// "a[i][j0] -> a[i][j1]" means a[i][j1] is better
// a: totally monotone <=> for i0 < i1:
//   a[i0][j0] -> a[i0][j1] ==> a[i1][j0] -> a[i1][j1]
//   a[i0][j0] <- a[i0][j1] <== a[i1][j0] <- a[i1][j1]
// cmp(i, j0, j1): "a[i][j0] -> a[i][j1]"
//   called only for j0 < j1
//   for a[i][j0] = a[i][j1]:
//     false to prefer smaller index
//     true to prefer larger index

namespace smawk_impl {
constexpr int MAX_M = 1 << 20;
constexpr int MAX_N = 1 << 20;
int is0[2 * MAX_M], js0[max(2 * MAX_M, MAX_N)];
template <class Cmp> struct Smawk {
  const int m, n;
  const Cmp cmp;
  vector<int> jms;
  Smawk(int m_, int n_, Cmp cmp_) : m(m_), n(n_), cmp(cmp_) {
    for (int i = 0; i < m; ++i) is0[i] = i;
    for (int j = 0; j < n; ++j) js0[j] = j;
    jms.assign(m, -1);
    rec(is0, m, js0, n);
  }
  void rec(int *is, int isLen, int *js, int jsLen) {
    if (!isLen || !jsLen) return;
    if (isLen < jsLen) {
      int len = 0;
      for (int y = 0; y < jsLen; ++y) {
        const int j = js[y];
        for (; len && cmp(is[len - 1], js[len - 1], j); --len) {}
        if (len != isLen) js[len++] = j;
      }
      jsLen = len;
    }
    int *iis = is + isLen, *jjs = js + jsLen;
    int iisLen = 0;
    for (int x = 1; x < isLen; x += 2) iis[iisLen++] = is[x];
    for (int y = 0; y < jsLen; ++y) jjs[y] = js[y];
    rec(iis, iisLen, jjs, jsLen);
    for (int x = 0, y = 0; x < isLen; x += 2) {
      const int i = is[x];
      const int j1 = (x + 1 < isLen) ? jms[is[x + 1]] : js[jsLen - 1];
      for (; ; ) {
        const int j = js[y];
        if (!~jms[i] || cmp(i, jms[i], j)) jms[i] = j;
        if (j == j1) break;
        ++y;
      }
    }
  }
};
}  // smawk_impl
template <class Cmp> vector<int> smawk(int m, int n, Cmp cmp) {
  return smawk_impl::Smawk<Cmp>(m, n, cmp).jms;
}

// cs[k] = \min[i+j=k] (as[i] + bs[j])
// as: convex
template <class T>
vector<T> minPlusConvolveConvex(const vector<T> as, const vector<T> &bs) {
  const int asLen = as.size(), bsLen = bs.size();
  if (!asLen || !bsLen) return {};
  const auto jms = smawk(asLen + bsLen - 1, bsLen, [&](int i, int j0, int j1) -> bool {
    if (i - j0 >= asLen) return true;
    if (i - j1 < 0) return false;
    return (as[i - j0] + bs[j0] > as[i - j1] + bs[j1]);
  });
  vector<T> cs(asLen + bsLen - 1);
  for (int i = 0; i < asLen + bsLen - 1; ++i) cs[i] = as[i - jms[i]] + bs[jms[i]];
  return cs;
}


constexpr Int INF = 1001001001001001001LL;

int N, Q;
vector<Int> A, B;
vector<int> O, P, L, R, K;
vector<Int> X, Y;

vector<Int> brute() {
cerr<<"[brute]"<<endl;
  auto as = A, bs = B;
  vector<Int> ans(Q, 0);
  for (int q = 0; q < Q; ++q) {
    if (O[q] == 1) {
      as[P[q]] = X[q];
      bs[P[q]] = Y[q];
    } else {
      vector<Int> dp(2 * (R[q] - L[q]) + 1, INF);
      dp[0] = 0;
      for (int i = L[q]; i < R[q]; ++i) {
        for (int k = 2 * (i - L[q]); k >= 0; --k) {
          chmin(dp[k + 1], dp[k] + as[i]);
          chmin(dp[k + 2], dp[k] + bs[i]);
        }
      }
      ans[q] = dp[K[q]];
    }
  }
  return ans;
}

namespace sub4 {
vector<Int> build(int l, int r) {
  vector<Int> easy;
  vector<pair<Int, Int>> hard;
  for (int i = l; i < r; ++i) {
    if (A[i] <= B[i] - A[i]) {
      easy.push_back(A[i]);
      easy.push_back(B[i] - A[i]);
    } else {
      hard.emplace_back(B[i], A[i]);
    }
  }
  sort(easy.begin(), easy.end());
  sort(hard.begin(), hard.end());
  const int easyLen = easy.size();
  const int hardLen = hard.size();
  vector<Int> fs(easyLen + 1, 0);
  for (int j = 0; j < easyLen; ++j) fs[j + 1] = fs[j] + easy[j];
  vector<Int> pre(hardLen + 1, -INF), suf(hardLen + 1, INF);
  for (int j = 0; j < hardLen; ++j) pre[j + 1] = max(pre[j], hard[j].first - hard[j].second);
  for (int j = hardLen; --j >= 0; ) suf[j] = min(hard[j].second, suf[j + 1]);
  vector<Int> gs(hardLen * 2 + 1, INF);
  gs[0] = 0;
  for (int j = 0; j < hardLen; ++j) gs[(j + 1) * 2] = gs[j * 2] + hard[j].first;
  for (int j = 0; j <= hardLen; ++j) {
    if (j > 0) chmin(gs[j * 2 - 1], gs[j * 2] - pre[j]);
    if (j < hardLen) chmin(gs[j * 2 + 1], gs[j * 2] + suf[j]);
  }
  const auto ret = minPlusConvolveConvex(fs, gs);
// cerr<<l<<" "<<r<<": "<<ret<<endl;
  return ret;
}

vector<Int> run() {
cerr<<"[sub4::run]"<<endl;
// for(int l=0;l<N;++l)for(int r=l+1;r<=N;++r)build(l,r);
  const int block = sqrt(N);
  vector<vector<int>> qss(N / block + 1);
  for (int q = 0; q < Q; ++q) qss[R[q] / block].push_back(q);
  vector<Int> ans(Q, 0);
  for (int x = 0; x <= N / block; ++x) if (qss[x].size()) {
    const auto giant = build(0, x * block);
    for (const int q : qss[x]) {
      const auto baby = build(x * block, R[q]);
      ans[q] = INF;
      for (int k = 0; k < (int)baby.size(); ++k) {
        const int kk = K[q] - k;
        if (0 <= kk && kk < (int)giant.size()) {
          chmin(ans[q], giant[kk] + baby[k]);
        }
      }
    }
  }
  return ans;
}
}  // sub4

int main() {
  for (; ~scanf("%d%d", &N, &Q); ) {
    A.resize(N);
    B.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld%lld", &A[i], &B[i]);
      assert(0 < A[i]); assert(A[i] < B[i]);
    }
    O.assign(Q, -1);
    P.assign(Q, -1);
    L.assign(Q, -1);
    R.assign(Q, -1);
    K.assign(Q, -1);
    X.assign(Q, -1);
    Y.assign(Q, -1);
    for (int q = 0; q < Q; ++q) {
      scanf("%d", &O[q]);
      if (O[q] == 1) {
        scanf("%d%lld%lld", &P[q], &X[q], &Y[q]);
        assert(0 <= P[q]); assert(P[q] < N);
        assert(0 < X[q]); assert(X[q] < Y[q]);
      } else if (O[q] == 2) {
        scanf("%d%d%d", &L[q], &R[q], &K[q]);
        ++R[q];
        assert(0 <= L[q]); assert(L[q] < R[q]); assert(R[q] <= N);
      } else {
        assert(false);
      }
    }
    
    vector<Int> ans;
    if (L == vector<int>(Q, 0)) {
      ans = sub4::run();
    } else {
      ans = brute();
    }
    for (int q = 0; q < Q; ++q) if (O[q] == 2) {
      printf("%lld\n", ans[q]);
    }
  }
  return 0;
}