**Solution Notes:** The problem is solved by "brute force", by
enumerating through all possible subsets of cows and keeping track of
the largest one that fits on the raft. One way to do this enumeration
is recursively, shown in the code below, where we consider cow #1 and
then recursively enumerate all solutions that do contain cow #1, and
then all solutions that do not contain cow #1. Along the way, we
prune the search and backtrack if we ever notice that our current
solution is infeasible (i.e., if it generates a carry), or if the
number of cows remaining plus the number of cows we have used so far
cannot possibly do better than the best solution we have generated
thus far.

Another nice "trick" for enumerating all 2^20 subsets of cows for this problem is to simply count from 0 up to 2^20-1. The 0s and 1s in the binary representation of our integer counter tell us a particular subset, and we will generate every possible subset as we count. For example, if the counter is (in binary) 10011000000000000000, then this means we are considering a subset that includes cows 1, 4, and 5 (the positions of the 1 bits).

```
#include <fstream>
using namespace std;
int n, w[20], best=0;
/* Can x and y be added with no carries? */
int check(int x, int y)
{
for ( ; x>0 && y>0; x/=10,y/=10)
if (x%10+y%10>=10) return 0;
return 1;
}
/*
x = index into w array we're currently considering (i.e., we have already
added a subset of w[1...x-1] and are considering whether to add w[x]).
sum = cumulative sum of subset added so far.
count = number of elements in subset added so far.
*/
void rec(int x, int sum, int count)
{
if (count>best) best=count;
if (x>=n || count+n-x<=best) return;
if (check(sum,w[x]))
rec(x+1,sum+w[x],count+1);
rec(x+1,sum,count);
}
int main()
{
ifstream fin("escape.in");
ofstream fout("escape.out");
fin >> n;
for (int i=0; i<n; i++)
fin >> w[i];
fin.close();
rec(0,0,0);
fout << best << endl;
fout.close();
return 0;
}
```