6350: 健康的荷斯坦奶牛

内存限制:256 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:2 通过:2

题目描述

农夫约翰以拥有世界上最健康的奶牛而感到自豪。

奶牛想要保持健康,每天就要补充足量的多种维生素。

约翰为奶牛们准备了多种牛饲料,每种牛饲料中都富含奶牛所需的多种维生素,但是每种维生素的具体含量可能并不相同。

每种牛饲料每天最多只能喂给奶牛们一勺,也就是说每种饲料可以选择不喂给奶牛,或喂给奶牛一勺的量。

现在给定所有饲料的每种维生素的(每勺)具体含量,以及奶牛对于每种维生素的每日最低需求量。

请你求出,保证奶牛各种维生素的每日摄入量达标的情况下,最少需要喂给奶牛多少勺饲料。

数据保证有解。

输入格式

第一行包含一个整数 V,表示共有 V 种所需维生素,编号 1∼V。 

第二行包含 V 个不超过 1000 的正整数,其中第 i个数表示第 i 号维生素的奶牛每日最低需求量。 
第三行包含整数 G,表示牛饲料的种类数。
接下来 G 行,每行包含 V 个不超过 1000 的非负整数,其中第 i 个数表示一种饲料中第 i 号维生素的含量(每勺)。

输出格式


共一行,首先输出一个整数 S,表示最少需要喂给奶牛的饲料数量,接下来输出 S 个升序排列的整数,表示喂给奶牛的饲料的具体编号。

当存在多个解时,输出序列字典序最小的那个解。

数据范围

51≤V≤25,
1≤G≤15

输入样例 复制

4
100 200 300 400
3
50 50 50 50
200 300 200 300
900 150 389 399

输出样例 复制

2 1 3

分类标签