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

#define fi first
#define se second
#define mk make_pair

const int INF = 1e9;

int W, ans;

int get_min_count(vector<int> a) {
	multiset<int> ms;
	for (int i = 0; i < (int)a.size(); ++i) {
		ms.insert(a[i]);
	}
	
	int res = 0;
	
	while (!ms.empty()) {
		int remaining = W;
		while (remaining > 0) {
			multiset<int>::iterator it = ms.upper_bound(remaining);
			if (it == ms.begin()) {
				break;
			}
			--it;
			remaining -= (*it);
			ms.erase(it);
		}
		
		res++;
	}
	
	return res;
}

int get_min_count2(vector<int> a, int lim) {
	multiset<int> ms;
	for (int i = 0; i < (int)a.size(); ++i) {
		ms.insert(a[i]);
	}
	
	int res = 0;
	
	while (!ms.empty()) {
		int remaining = (res ? W : lim); // use lim if it is the first time
		while (remaining > 0) {
			multiset<int>::iterator it = ms.upper_bound(remaining);
			if (it == ms.begin()) {
				break;
			}
			--it;
			remaining -= (*it);
			ms.erase(it);
		}
		
		res++;
	}
	
	return res;
}

int dfs() {
	int m, num;
	cin >> m >> num;
	
	vector<int> a;
	
	for (int i = 1; i <= num; ++i) {
		int x = dfs();
		assert(x < W);
		if (x > 0) {
			a.push_back(x);
		}
	}
	
	pair<int, int> res = mk(INF, INF);
	if (m < W) { // CASE 1: don't cut, not even at the very top (i.e., the returned weight >= m)
		vector<int> tmp = a;
		tmp.push_back(m);
		int mc = get_min_count(tmp);
		
		int l = m, r = W;
		while (l < r) {
			int mid = (l + r) / 2;
			if (get_min_count2(a, mid - m) == mc) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		
		if (l == W) {
			res = mk(mc, 0);
		} else {
			res = mk(mc - 1, l);
		}
	}
	
	// CASE 2: cut (means that we will give something down)
	int mc = get_min_count(a);
	int l = 0, r = min(m, W);
	while (l < r) { // give down as much (large) as possible
		int mid = (l + r + 1) / 2;
		
		vector<int> tmp = a;
		tmp.push_back(mid);
		
		if (get_min_count(tmp) == mc) {
			l = mid;
		} else {
			r = mid - 1;
		}
	}
	
	int len = m - l;
	res = min(res, mk(mc + len / W, len % W));
	
	ans += res.fi;
	
	return res.se;
}

int main() {
	cin >> W;
	if (dfs()) {
		ans++;
	}
	cout << ans << endl;
	return 0;
}