题目描述

某地区近期遭遇严重干旱，政府需要紧急采购饮用水以满足居民基本需求。当地有多家水供应商，每家供应商的水价和供应量各不相同。政府需要在保证供水总量的前提下，最小化采购成本。

政府每天需要采购固定数量的饮用水（$n$ 吨）。市场上有 $m$ 家水供应商，每家供应商有以下两个属性：

供水价格：$p_i$ 元/吨
供应上限：每天最多能提供 $a_i​$ 吨

采购要求：

• 可以从每家供应商购买任意数量的水，不超过其供应上限
• 必须确保采购总量满足居民需求
• 目标是使总采购成本最低

输入格式

第一行：两个整数 $n$ 和$m$，依次表示每天需要的饮用水总量（吨）和水供应商数量。

接下来 $m$ 行表示每个供应商的信息。

每行两个整数 $p_i$​ 和 $a_i$​，依次表示供应商的水价（元/吨）和该供应商的最大供应量（吨）

输出格式

输出一个整数，表示采购所需饮用水的最小总成本。如果无法满足供应量，输出 $-1$。

输入输出样例

200 4
3 50
5 100
4 80
6 120

820

数据范围与提示

• $0 ≤ n ≤ 2000000$
• $0 ≤ m ≤ 5000$
• $0 ≤ a_i​ ≤ 2,000,000$
• $0 ≤ p_i ≤ 1,000$