Knapsack Problem

The knapsack problem is stated as follows. There are $n$ items, and the $i$-th item has weight $w\_i$ and value $v\_i$. The task is to choose a set of items with maximum total value such that their total weight does not exceed $c$, the capacity of the knapsack. The knapsack problem is NP-hard, but it can be solved with dynamic programming in time proportional to the total weight of the items.

However, the knapsack problem can be solved greedily in some cases. One such case is when an instance of the knapsack problem forms a matroid.

A matroid is a pair $\langle X, {\cal I}\rangle$, where $X$ is a finite set and $\cal I$ is a family of subsets of $X$. The elements of $\cal I$ are called independent. The family $\cal I$ must satisfy the following axioms.

1. ${\cal I} \ne \varnothing$;
2. If $A \in {\cal I}$ and $B \subset A$, then $B \in {\cal I}$;
3. If $A, B \in {\cal I}$ and $|A| > |B|$, then there exists $x \in A \setminus B$ such that $B \cup \{x\}\in{\cal I}$.

Here $|A|$ is the number of items in the set $A$.

An example of a matroid is the set of edges of an undirected graph, where an edge set is independent if it is acyclic.

Let the items have weights $w\_1, w\_2, \ldots, w\_n$, and take these items as $X$. A set of items $\{i\_1, i\_2, \ldots, i\_k\}$ is called independent if $w\_{i\_1}+w\_{i\_2}+\ldots+w\_{i\_k} \le c$. Determine whether this construction forms a matroid for the given $w\_1, w\_2, \ldots, w\_n$ and $c$.

The first line contains an integer $n$ ($1 \le n \le 50$). The second line contains $n$ integers $w\_1, w\_2, \ldots, w\_n$ ($1 \le w\_i \le 100$). The third line contains an integer $c$ ($\max w\_i \le c \le \sum w\_i$).

Print YES if the set of solutions to the knapsack problem forms a matroid. Otherwise, print NO.

In the second case, print on the second line one integer, the number of the axiom that is violated. If axiom 2 or axiom 3 is violated, print on the next two lines the sets $A$ and $B$ for which the axiom does not hold. Each set is described by the number of items in it, followed by the numbers of those items.