2810 - 科学饮食

题目描述

一位着迷于保持身体健康的科学家,通过研究发现了人体所需的多种微量元素。

他决定通过合理搭配不同的食材,使自己的饮食更加科学。为了实现这一目标,科学家希望你帮他选择最少的食材,确保每种微量元素的摄入量满足最低需求

给定各种微量元素的最低需求,你需要输出选择的食材,使得所需食材的种类最少

微量元素量以整数表示,每种食材最多只能使用一次,数据保证存在解。

输入

第一行一个整数 n,表示微量元素的种类数。

第二行 n 个整数,表示每天需要的每种微量元素的最小量。

第三行一个整数 m,表示可供选择的食材的种数。

接下来 m 行,第 i 行表示编号为 i 的食材含有各种微量元素的量的多少。

输出

输出只有一行

先输出所需的最小食材种数 c

后面有 c 个数,表示所选择的食材编号(按从小到大排列)。

如果有多个解,输出食材序号最小的解(即字典序最小)。

样例

输入

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

输出

2 1 3

输入

8
10 10 10 10 10 10 15 12
7
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4
100 100 100 100 100 100 0 0
5 5 5 5 5 5 10 0
5 5 5 5 5 5 0 10

输出

4 1 4 6 7
说明

数据范围

对于 100\% 的数据,1\le n \le 251\le m \le 15

输入的所有整数在 [1,1000] 范围内。

来源

USACO 2.1

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 244
通过人数 108
金币数量 0 枚
难度 入门


上一题 下一题