[网络流24题]太空飞行计划问题
题号:NC213816
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em},和进行这些实验需要使用的全部仪器的集合I={I1,I2,…In}。实验Ej需要用到的仪器是I的子集。配置仪器I_k的费用为c_k美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
编程任务:对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。

输入描述:

第1行有2 个正整数m和n。m是实验数,n是仪器数。接下来的m 行,每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用;接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。

输出描述:

程序运行结束时,将最佳实验方案输出。第1 行是实验编号;第2行是仪器编号;最后一行是净收益。

示例1

输入

复制
2 3
10 1 2
25 2 3
5 6 7

输出

复制
1 2
1 2 3
17

备注:

1≤n,m≤50