题目描述

人体每天需要摄入 $n$ 种微量元素，第 $j$ 种微量元素的最低需求量为 $a_j$。现在有 $m$ 种食材，第 $i$ 种食材中第 $j$ 种微量元素的含量为 $b_{i,j}$。每种食材最多选择一次。

请选择尽可能少的食材，使每种微量元素的总含量都不低于对应的最低需求量。题目保证存在满足要求的选择方案。

如果有多种使用食材数量相同的最优方案，输出食材编号序列字典序最小的方案。

输入格式

第一行包含一个整数 $n$，表示微量元素的种类数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每种微量元素的最低需求量。

第三行包含一个整数 $m$，表示食材的种类数。

接下来 $m$ 行，每行包含 $n$ 个整数。第 $i$ 行的第 $j$ 个整数 $b_{i,j}$ 表示第 $i$ 种食材中第 $j$ 种微量元素的含量。

输出格式

输出一行。先输出最少需要选择的食材数量，再按从小到大的顺序输出所选食材的编号，所有整数之间用一个空格分隔。

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

2 1 3

数据范围与提示

• $1 \le n \le 25$
• $1 \le m \le 15$
• $1 \le a_j,b_{i,j} \le 1000$