#P2700. 聚会

    ID: 1794 传统题 1000ms 128MiB 尝试: 97 已通过: 34 难度: 5 上传者: 标签>CF1800普及+/提高-排序贪心交换论证线性 DP状态维度消除滚动数组

聚会

题目描述

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

输入格式

输入第一行两个数 mm 和 nn,下面 nn 行每行两个数 cic_i 和 sis_i,cic_i 为第 ii 种茶的单价,si=1s_i=1 表示第 ii 种茶是红茶,si=0s_i=0 表示第 ii 种茶是绿茶。

输出格式

输出第一行为最小总花费

3 4
1 0
2 0
4 1
3 1
10

样例说明:

第一次泡单价 11 的绿茶,花费 1×31\times 3;第二次泡单价 22 的绿茶,花费 2×22\times 2;第三次泡单价 33 的红茶,花费 3×13\times 1。总花费 3+4+3=103+4+3=10。

数据规模与约定

  • 对于 20%20\% 的数据满足 1≤m≤n≤101 \le m \le n \le 10。
  • 对于 50%50\% 的数据满足 1≤m≤n≤1001 \le m \le n \le 100。
  • 对于 100%100\% 的数据满足 1≤m≤n≤103,1≤ci≤1051 \le m \le n \le 10^3,1 \le c_i \le 10^5。