#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

const int T = 1e6 + 7;
const int A = 5e4 + 7;

int a, b, t;
int x[A], y[A];
int w[T], s[T];
vector<int> xs, ys;
int nx, ny;
vector<int> byw[A];
int c[A];
int fx[A], fy[A];

bool check(int k) {
	for (int i = 0; i <= ny; ++i) {
		c[i] = 0;
	}
	for (int wp = nx; wp >= 0; --wp) {
		for (int i : byw[wp]) {
			for (int j = 0; j <= s[i]; ++j) {
				++c[j];
			}
		}
		for (int sp = 0; sp <= ny; ++sp) {
			if (c[sp] > k * (fx[wp] + fy[sp])) {
				return 0;
			}
		}
	}
	return 1;
}

}

int putaway(int grda, int grdb, int grdt, int grdx[], int grdy[], int grdw[], int grds[]) {
	a = grda;
	b = grdb;
	t = grdt;
	for (int i = 0; i < a; ++i) {
		x[i] = grdx[i];
	}
	for (int i = 0; i < b; ++i) {
		y[i] = grdy[i];
	}
	for (int i = 0; i < t; ++i) {
		w[i] = grdw[i];
		s[i] = grds[i];
	}
	for (int i = 0; i < a; ++i) {
		xs.push_back(x[i]);
	}
	for (int i = 0; i < b; ++i) {
		ys.push_back(y[i]);
	}
	sort(xs.begin(), xs.end());
	xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
	sort(ys.begin(), ys.end());
	ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
	nx = xs.size();
	ny = ys.size();
	for (int i = 0; i < a; ++i) {
		x[i] = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin();
	}
	for (int i = 0; i < b; ++i) {
		y[i] = lower_bound(ys.begin(), ys.end(), y[i]) - ys.begin();
	}
	for (int i = 0; i < t; ++i) {
		w[i] = upper_bound(xs.begin(), xs.end(), w[i]) - xs.begin();
		s[i] = upper_bound(ys.begin(), ys.end(), s[i]) - ys.begin();
		if (w[i] == nx && s[i] == ny) {
			return -1;
		}
	}
	for (int i = 0; i < t; ++i) {
		byw[w[i]].push_back(i);
	}
	for (int i = 0; i < a; ++i) {
		++fx[x[i]];
	}
	for (int i = 0; i < b; ++i) {
		++fy[y[i]];
	}
	for (int i = nx - 1; i >= 0; --i) {
		fx[i] += fx[i + 1];
	}
	for (int i = ny - 1; i >= 0; --i) {
		fy[i] += fy[i + 1];
	}
	int l = 0, r = t;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		if (check(mid)) {
			r = mid;
		} else {
			l = mid;
		}
	}
	return r;
}