logo AlgoBeat OnlineJudge
登录 注册

#214040. [ICPC 2023 Nanjing R] 电梯

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

组包裹需要被配送。第 组共有 个包裹,每个包裹的重量为 等于 ),并且需要被送到第 层。

有一台电梯,每趟能运送总重量不超过 是偶数)的包裹。电梯会从地面层出发,渐渐移动到这一趟所有包裹的目标楼层的最高层 ,最后返回地面层。这一趟运送将消耗 单位的电能。

更正式地,令 表示一个重量为 ,且目的地为第 层的包裹。一个由包裹组成的多重集合(一种可能含有重复元素的集合) 能在同一趟被运送,若 。这一趟运送将消耗 单位的电能。

求将所有包裹运送到目的地最少一共需要多少单位的电能?

请注意,每一趟运送的包裹可以来自不同组,每一组包裹也可以分成多趟运送。您可以认为一共有 个包裹需要被运送,只不过一些包裹可能有相同的重量以及相同的目的地。

输入格式

有多组测试数据。第一行输入一个整数 表示测试数据组数,对于每组测试数据:

第一行输入两个整数 是偶数)表示组数以及电梯的最大载重。

对于接下来 行,第 行输入三个整数 )表示第 组包裹的数量,每个包裹的重量以及目的地。

保证所有数据中 之和不超过

输出格式

每组数据输出一行一个整数,表示将所有包裹运送到目的地最少一共需要多少单位的电能。

样例

样例输入 1

2
4 6
1 1 8
7 2 5
1 1 7
3 2 6
8 1200000
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345

样例输出 1

24
100000

数据范围与提示

对于第一组样例数据,我们可以遵循以下策略:

  • 第一趟运送包裹 。这一趟消耗 单位的电能。
  • 第二趟运送包裹 。这一趟消耗 单位的电能。
  • 第三趟运送包裹 。这一趟消耗 单位的电能。
  • 第四趟运送包裹 。这一趟消耗 单位的电能。

一共需要 单位的电能。可以证明这是最少一共需要的电能。

对于第二组样例数据,所有包裹可以在同一趟被运送。