一位着迷于保持身体健康的科学家,通过研究发现了人体所需的多种微量元素。
他决定通过合理搭配不同的食材,使自己的饮食更加科学。为了实现这一目标,科学家希望你帮他选择最少的食材,确保每种微量元素的摄入量满足最低需求。
给定各种微量元素的最低需求,你需要输出选择的食材,使得所需食材的种类最少。
微量元素量以整数表示,每种食材最多只能使用一次,数据保证存在解。
第一行一个整数 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 25,1\le m \le 15。
输入的所有整数在 [1,1000] 范围内。
USACO 2.1