You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

「UOI R2」时间规划

题目背景

Crazyouth 发现自己的 OI 水平有待提高，只能抓紧恶补了 qwq。

题目描述

Crazyouth 在接下来的时间里有 $n$ 个小时的时间学习高级的算法，他的目标是学习 $k$ 个算法，学第 $i$ 个算法学习所需的时间是 $a_i$ 小时，而这些算法的种类分 $m$ 种，第 $i$ 个算法的种类是 $b_i$。然而，学习同一种算法是会让人疲倦的。

如果他学习了一个种类的算法，那么下次他学习所有该种类算法的时间增加 $a_i$，这里的 $a_i$ 指的是学习该算法所需的初始时间而非现在所需的时间。例如他学习了第 $1$ 种类的算法 $3$ 个，那么他学第二个第 $1$ 种类的算法的时间变为原来的 $2$ 倍，第三个变为 $3$ 倍，以此类推。

现在 Crazyouth 想知道他在这个月内最多可以学习多少算法，其时间总和不超过 $n$ 小时。

输入格式

第一行，三个整数，分别代表 $n,k,m$。

接下来 $k$ 行，每行两个整数，分别表示 $a_i$ 和 $b_i$。

输出格式

一个整数，表示 Crazyouth 在这个月内最多能学习的算法数。

样例 #1

样例输入 #1

10 3 2
4 2
6 2
6 1

样例输出 #1

2

提示

样例解释

他最多只能学算法 $1$ 和算法 $3$。

数据范围

本题使用捆绑测试。

对于 $100\%$ 的数据，保证 $1\le a_i\le n\le 10^{10}$，$1 \le k\le 10^3$，$1\le b_i\le m\le 5$。