/* lecount -- count picks that sum to less than or equal a target
 * 
 * unsigned	cn;
 * unsigned	cndv;
 * unsigned	cts;
 * long		l, e;
 * lecount(cn, cndv, cts, &l, &e);
 *
 * lecount counts the number of picks of cn values that sum to < cts,
 * and that sum = cts, placing the results in l and e respectively.
 * The values are chosen from the first cndv value-frequency pairs in
 * avf.  lecount assumes the problem has been properly massaged by
 * legpicks beforehand.
 */
static void
lecount(cn, cndv, cts, lp, ep)
unsigned	cn;
unsigned	cndv;
unsigned	cts;
long		*lp;
long		*ep;
{
    register int	i;
    register int	v, f;
    int			ccn, ccts, ccndv;
    long		l, e;
    long		ls, es;
    long		pfi;		/* pick(f, i)			*/

    indent++;
    *lp = *ep = 0L;
    /*
     * make sure inputs valid
     */
    if (cndv <= 0) error("Can't Happen");
    /*
     * prune some easily handled cases
     */
    if (
	(cts < cs[cn-1]) ||		/* any sum of cn is > cts	*/
	(cn > avf[cndv-1].cf)		/* there aren't cn vals		*/
    ) {
	dprint("Can't be done\n");
	*lp = *ep = 0L;
	goto leave;
    }
    /*
     * none to pick: sum is zero, and there's one way to pick nothing.
     */
    if (0 == cn) {
	if (cts == 0) *ep = 1L;		/* 1 works...			*/
	else *lp = 1L;			/* ...trust me			*/
	goto leave;
    }
    /*
     * Only one value available.  Because cts < cs[cn-1], we know we
     * can pick cn of this value and be <= cts.
     */
    if (1 == cndv) {			/* only one val left		*/
	pfi = pick(avf[0].freq, cn);	/* # ways to pick cn from freq	*/
	if (cs[cn-1] == cts) *ep = pfi;	/* exactly equal		*/
	else *lp = pfi;			/* less				*/
	goto leave;
    }
    /*
     * Only one to be picked.  Find the # of vals < cts.
     */
    if (1 == cn) {
	for(i=1; i<cndv; i++) {
	    if ((v = avf[i].val) > cts) break;
	}
	i--;
	if (v == cts) {			/* found an equal value		*/
	    *ep = avf[i].freq;		/* that many are equal		*/
					/* ...and all before are less	*/
	    *lp = (i > 0) ? avf[i-1].cf : 0L;
	}
	else {				/* no equal value found		*/
	    *lp = avf[i].cf;		/* all to this point are less	*/
	}
	goto leave;
    }
    /*
     * Both cn and cndv are >1.  Try to pick values from one of the
     * avf[i], and call lecount recursively to find compatible lower
     * picks.
     */
    ls = es = 0L;			/* accumulators for sums	*/
    for(ccndv=cndv; ccndv-- > 1;) {
	f = avf[ccndv].freq;		/* # we can pick		*/
	v = avf[ccndv].val;		/* what each one costs		*/
	ccn = cn;			/* current number to pick	*/
	ccts = cts;			/* current target sum		*/
	pfi = 1L;			/* pick(f, i)			*/
	for(i=1; i<=f; i++) {		/* i = # of this val to use	*/
	    if (ccts < v) break;	/* we can't afford any more	*/
	    ccn--;			/* OK: Buy one of these		*/
	    ccts -= v;			/* ...and pay for it		*/
	    pfi *= f+1 - i;		/* how many ways we can do it	*/
	    pfi /= i;
					/* now find lower picks that fit*/
	    if (0 == ccn) {		/* (lecount doesn't like 0's)	*/
		if (ccts == 0) es += pfi;
		else ls += pfi;
		break;			/* no more can be taken		*/
	    }
	    lecount(ccn, ccndv, ccts, &l, &e);
	    if (dflag) dprint("%ld * %ld = %ld < %d + %d * %d = %d\n",
		l, pfi, pfi * l, ccts, v, i, cts
	    );
	    ls += pfi * l;		/* sum up			*/
	    es += pfi * e;
	}
    }
    lecount(cn, 1, cts, &l, &e);	/* handle cndv == 1		*/
    *lp = ls += l;
    *ep = es += e;

leave:
    if (dflag) dprint("%ld <, %ld == %d, %d vals chosen from 1st %d \n",
	*lp, *ep, cts, cn, cndv
    );
    indent--;
}