聚会

内存限制：128 MiB 时间限制：10 Sec

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

输入第一行两个数M和N，下面N行每行两个数ci和si，ci为第i种茶的单价，si=1表示第i种茶是红茶，si=0表示第i种茶是绿茶。

输出第一行为最小总花费，样例数据

输入

输出

说明

3 4

1 0

2 0

4 1

3 1

10

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

数据规模

对于20%的数据满足1 ≤ M ≤ N ≤ 10

对于50%的数据满足1 ≤ M ≤ N ≤ 100

对于100%的数据满足1 ≤ M ≤ N ≤ 1000，1 ≤ ci ≤ 100000

样例输入

样例输出

BZPRO Powered by XZYQvQ.
Github Repository

#2700. 聚会

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

输入	输出	说明
3 4 1 0 2 0 4 1 3 1	10	第一次泡单价1的绿茶，花费13；第二次泡单价2的绿茶，花费22；第三次泡单价3的红茶，花费3*1。总花费3+4+3=10。