#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>
#include <map>
#include <array>
#include <cmath>

using namespace std;

long long PRIME = 1000000007;


struct info{
    long long b;
    long long l;
    long long u;
    long long d_max;
};


bool comp(const info& l, const info& r){
    return l.d_max > r.d_max;
}


vector<info> info_vec;
vector<long long> sum_vec;
long long X;
long long N;


long long checkX(long long S){
    long long num = S / X;
    long long rest = S % X;

    if(rest == 0){
        return sum_vec[num];
    }

    long long ret = -1;

    for(int i = 0; i < N; ++i){
        long long val;

        if(i < num){
            val = sum_vec[num + 1];
            val -= info_vec[i].d_max;
        }
        else{
            val = sum_vec[num];
        }

        if(rest < info_vec[i].b){
            val += info_vec[i].l * rest;
        }
        else{
            val += info_vec[i].l * info_vec[i].b + info_vec[i].u * (rest - info_vec[i].b);
        }

        ret = max(ret, val);
    }

    return ret;
}


int main(int argc, char* argv[]){
    cin >> N >> X;

    info_vec.resize(N);
    sum_vec.resize(N + 1);

    long long b;
    long long l;
    long long u;

    long long cost_zero = 0;

    for(int i = 0; i < N; ++i){
        cin >> b >> l >> u;

        info_vec[i].b = b;
        info_vec[i].u = u;
        info_vec[i].l = l;
        info_vec[i].d_max = (X - b) * u + b * l;

        cost_zero -= l * b;
    }

    if(cost_zero == 0){
        cout << 0;
        return 0;
    }
    
    std::sort(info_vec.begin(), info_vec.end(), comp);

    sum_vec[0] = cost_zero;
    for(int i = 1; i <= N; ++i){
        sum_vec[i] = sum_vec[i-1] +info_vec[i-1].d_max;
    }

    long long min_X = 0;
    long long max_X = X * N;
    long long mid_X;
    long long cost;

    while(max_X - min_X > 1){
        mid_X = (min_X + max_X) / 2;

        cost = checkX(mid_X);

        if(cost < 0){
            min_X = mid_X;
        }
        else{
            max_X = mid_X;
        }
    }

    cout << max_X;

}

#include <iostream>
#include <cstring>
#include <cstdio>

#define Maxn 4010
#define Maxm 4010

using namespace std;

int read() {
	int x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while('0' <= c && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

int N,M,Q;
int mp[Maxn][Maxm],sum1[Maxn][Maxm],sum2[Maxn][Maxm];

int main() {
	N = read(); M = read(); Q = read();
	char ch;
	for(int i = 1;i <= N; i++)
		for(int j = 1;j <= M; j++) {
			int x = i * 2 - 1,y = j * 2 - 1;
			ch = getchar();
			while(ch != '0' && ch != '1') ch = getchar();
			if(ch == '1') mp[x][y] = 1;
		}
	for(int i = 1;i <= N; i++)
		for(int j = 1;j <= M; j++) {
			int x = i * 2 - 1,y = j * 2 - 1;
			if(mp[x][y]) {
				if(mp[x - 2][y]) mp[x - 1][y] = 2;
				if(mp[x + 2][y]) mp[x + 1][y] = 2;
				if(mp[x][y + 2]) mp[x][y + 1] = 2;
				if(mp[x][y - 2]) mp[x][y - 1] = 2;
			}
		}
	for(int i = 1;i < N * 2; i++)
		for(int j = 1;j < M * 2; j++) {
			if(mp[i][j] == 1) sum1[i][j] = sum1[i - 1][j] + sum1[i][j - 1] - sum1[i - 1][j - 1] + 1;
			else sum1[i][j] = sum1[i - 1][j] + sum1[i][j - 1] - sum1[i - 1][j - 1];
			if(mp[i][j] == 2) sum2[i][j] = sum2[i - 1][j] + sum2[i][j - 1] - sum2[i - 1][j - 1] + 1;
			else sum2[i][j] = sum2[i - 1][j] + sum2[i][j - 1] - sum2[i - 1][j - 1];
		}
	int i_1,j_1,i_2,j_2,x_1,y_1,x_2,y_2;
	for(int k = 1;k <= Q; k++) {
		i_1 = read(); j_1 = read(); i_2 = read(); j_2 = read();
		x_1 = i_1 * 2 - 1; y_1 = j_1 * 2 - 1;
		x_2 = i_2 * 2 - 1; y_2 = j_2 * 2 - 1;
		int ans1 = sum1[x_2][y_2] + sum1[x_1 - 1][y_1 - 1] - sum1[x_2][y_1 - 1] - sum1[x_1 - 1][y_2];
		int ans2 = sum2[x_2][y_2] + sum2[x_1 - 1][y_1 - 1] - sum2[x_2][y_1 - 1] - sum2[x_1 - 1][y_2];
		printf("%d\n",ans1 - ans2);
	}
	return 0;
}