6700: BZOJ2700:聚会

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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


样例输入


样例输出


提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: