「MGOI Round 1 C」LaoPi的女装

「MGOI Round 1 C」LaoPi的女装

前奏

青春有各种不同的样子,我很庆幸我的青春有穿着女装的样子。 ————by LaoPi

本故事完全真实,之后会附上图片

题目背景

IX 和 LaoPi 一起回家,由于他们的生活过于平淡,于是他们开始找(fan)刺激(jian)。

他们看到前面有一个工地,于是

LaoPi:我赌前面肯定过不去,我试过了。
IX:绝对能过去,过不过去我女装。
LaoPi:嗯,如果过得去我女装,很公平。
IX: +1

他们走着,初时只见一面墙,IX绝望了,然而,突然发现了一座小(gou)门(dong), ......

题目描述

LaoPi被迫女装, IX想要让他变滴无比珂爱。
全世界只有n件女装,而其中又有m种类,Laopi每种类至多只能选1件,而每件衣服和其他衣服搭配的珂爱程度为\(a_i\)
我们称一套衣服的珂爱程度为所含衣服两两之间的珂爱度之和。
现在求能搭配出来的最大珂爱程度

输入格式

第一行两个整数\(n, m\), 分别表示共有多少件女装可供选择,和分为多少类
后面有\(2n\)行, 分为n个部分别描述n件女装。
每个部分有两行。第一行一个整数\(Type\),表示种类, 保证 \(Type\)是\(1\) 到 \(m\)间的整数
第二行n个整数\(a_i\),分别表示这种女装和第i种的搭配珂爱程度

输出格式

一行一个数, 表示最大的珂爱程度

输入输出样例

输入 #1

4 3
1
0 10 10 10
1
3 0 3 3
2
10 10 0 10
3
10 10 10 0

输出 #1

30

样例解释

选择1, 3, 4件服装组成,可以得到最大珂爱值30

说明

1. \(a_i\)可能为负数
2.题目数据保证合理,不会出现自相矛盾的情况

数据范围

对于 \(100\%\) 的数据,\(0 < n, m\le 200\),\(0 < a_i\le 10^5\), 并保证 ans 在int范围内。

限制

0.8s

信息

ID
1002
难度
5
分类
(无)
标签
递交数
2
已通过
1
通过率
50%
上传者

相关

在下列比赛中:

MGOI Round 1