AdditionalFile3859.zip

#3859. 「POI 2020/2021 R1」Cukiernia

标签: 传统 | 时间限制: 1000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXVIII Olimpiada Informatyczna – I etap Cukiernia

Bajtuś 面包店售卖蛋糕，甜甜圈和羊角面包三种食物。在面包店中，有 $n$ 个橱窗，在正常情况下，每个货架上只应该放置一种食物。但一天早上，面包店老板 Bajtazara 的儿子 Bajtuś 偷偷进入了面包店，将所有的食物摆放得乱七八糟。

面包店马上就要开门了，Bajtazara 急切地想要重新摆放食物，使得每个货架上只有一种食物（特别地，一个货架上没有食物也是允许的）。请你帮助他求出，至少需要移动多少次食物才能达成目标。

输入格式

输入数据第一行包含一个整数 $n$，代表面包店中货架的数量。

接下来 $n$ 行，第 $i$ 行包含三个整数 $d_i,p_i,r_i$，分别代表该货架上现有的蛋糕数，甜甜圈数和羊角面包数。数据保证面包店中至少有一份食物。

输出格式

输出一个整数，代表需要移动食物的最小次数。

样例 1

输入

5
5 1 1
0 3 4
1 4 3
4 0 0
0 0 0

输出

9

一种合法的移动方案如下：

1. 将一个甜甜圈从货架 $1$ 移动至货架 $3$，将一个羊角面包从货架 $1$ 移动至货架 $2$；
2. 将三个甜甜圈从货架 $2$ 移动至货架 $3$；
3. 将一个蛋糕从货架 $3$ 移动至货架 $1$，将三个羊角面包从货架 $3$ 移动至货架 $2$；

在此之后，货架 $1$ 只有蛋糕，货架 $2$ 只有羊角面包，货架 $3$ 只有甜甜圈，货架 $4$ 只有蛋糕，货架 $5$ 是空的。

样例 2

输入

3
1 1 2
2 1 1
1 1 2

输出

7

样例 3

输入

5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5

输出

50

样例 4

见附加文件下 [cuk3.in](file:cuk3.in) 和 [cuk3.out](file:cuk3.out)。

该样例中有 $1000$ 个货架，每个货架上有十个蛋糕或十个甜甜圈，该样例的输出为 $0$。

样例 5

见附加文件下 [cuk4.in](file:cuk4.in) 和 [cuk4.out](file:cuk4.out)。

该样例中有 $3 \times 10^5$ 个货架，每个货架上有三个蛋糕，两个甜甜圈，一个羊角面包。

数据范围与提示

所有测试点均满足：$3 \leq n \leq 3 \times 10^5$，$0 \leq d_i,p_i,r_i \leq 10^9$。