题目描述

Alice 正在组织一次有 $m$ 位同学参加的同学聚会。
Alice 有 $n$ 种不同的茶，每种茶有各自的单价和类别（红茶或绿茶）。
每隔一单位时间，聚会上都有一个同学离开。
Alice 希望安排一种泡茶的方案，每单位时间都给所有剩下的同学们泡同一种之前没有泡过的茶，花费就是此茶的单价乘以剩余的同学数。
同时，他不希望连续三次泡的茶都是红茶或都是绿茶。
请你找出一种方案，在满足上面的条件下使得总花费最小。
如果有多种方案，找出任意一种。保证存在解。

输入格式

输入第一行两个数 $m$ 和 $n$，下面 $n$ 行每行两个数 $c_i$ 和 $s_i$，$c_i$ 为第 $i$ 种茶的单价，$s_i=1$ 表示第 $i$ 种茶是红茶，$s_i=0$ 表示第 $i$ 种茶是绿茶。

输出格式

输出第一行为最小总花费

3 4
1 0
2 0
4 1
3 1

10

样例说明：

第一次泡单价 $1$ 的绿茶，花费 $1\times 3$；第二次泡单价 $2$ 的绿茶，花费 $2\times 2$；第三次泡单价 $3$ 的红茶，花费 $3\times 1$。总花费 $3+4+3=10$。

数据规模与约定

• 对于 $20\%$ 的数据满足 $1 \le m \le n \le 10$。
• 对于 $50\%$ 的数据满足 $1 \le m \le n \le 100$。
• 对于 $100\%$ 的数据满足 $1 \le m \le n \le 10^3，1 \le c_i \le 10^5$。