/* Note from the POTM-MASTER:  while the limit on entries is
	25,000 characters, I always give contestants the
	opportunity to add comments, expand variable names,
	"un-cstrip" their code, and do whatever they wish to
	make it more readable without changing the functionality
	of the code before it is posted on the web.		*/


    /*  POTM ENTRY:  indiana_dijones v7                         */
    /*  Your Name:   Chad Hurwitz                               */
    /*  Your email:  churritz@cts.com                           */
    /*  g++ (gnu c++)                                           */

#define NDEBUG 

#include <sys/times.h>
#define MAXTIME 566

#define INITTIME (MAXTIME/4)
#define CLK_TCK 100     

#define cost(_a) (_a)
#define mult(_a) ((_a)/16) // for floats!!!

#define MAXLEV 3

#define nu(_a) ((_a))
#define de(_a) (pow(_a,power))

/* may not be possible but : optimize better_longest, finding conflicts and not
 * re-evaluating if the bests don't conflict with the best taken out.  Or
 * perhaps, finding multipe bests and then picking them off and applying them
 * untill one level is exhausted or conflicts with the current tour, that
 * might at least lessen the number of reevaluations.
 */

/* LONGEST3
 * (2) you must compute the moves taken (M) and the min moves left to the sink
 * node (S) and the minimum moves from source to sink (T), S<T, if (M+S>limit)
 * then obviously you must stop the branching.  you may also want to stop if
 * ((T-S)/T < M/limit) that is if the progress to get to the sink node is
 * less advanced than the progress to fill the limit of moves, this means you
 * might run out of moves before your run out of chances to get to the sink
 * node.
 *
 */


/*
 * previous name thoughts: barf_bag djorn_djorg
 * two simple uses of dijikstras alg
 */
#include <stdio.h>
#include <time.h>
#include <assert.h>
#include <stdlib.h>
#include <math.h>
#define RMAX 0x7fffffff

#define MAXALT 255
#define MAXDIST 0x7ffffff /* maximum alt distance from any point to anypoint */
#define MAXQELEMS 40000    /* maximum queue elements */
#define SETPOS ((POS*)1)
#define MAXSIZE 255
#define MAXLIM ((20*MAXSIZE)-1)

#define max(_a,_b) (((_a)>(_b))?_a:(_b))
#define min(_a,_b) (((_a)<(_b))?_a:(_b))
#define sqr(_a) ((_a)*(_a))

#define SRAND(_t) srand(_t)
#define RANDINT(_min,_max) ((_min)+(int)(rand()%((_max)-(_min)+1)))
#define RANDFLOAT(_min,_max) ((_min)+(rand()*((_max)-(_min))/(float)RMAX))

#define INLINE inline

#define MARK_OK 0x1
#define MARK_FREE 0x2
#define MARK_EDGEEEEEEEE 0x4
#define MARK_FREEEEEEEEE 0x8
#define MARK_SHORTEST 0x10 // If not set then it's in longest path
#define MARK_LIMBRANCHED 0x20 // This is set for each branched in lim_bbranch
#define MARK_INQ 0x40
#define MARK_OUTQ 0x80
#define BHALFMAX max(MAXLEV,2)
#define AHALFMAX max(MAXLEV,2)
#define PATH_MAXIMIZE 0x1
#define PATH_STRICT 0x2
#define isbetw(_a,_b,_c) (((_a)>(_c)) \
 ? (_a)>=(_b) && (_b)>=(_c) : ((_c)>=(_b) && (_b)>=(_a)))

static float power;
typedef float best_t;
class node_t;
class PQ;
class POS {
public:
   int alt, dist;
   best_t qbest;
   node_t *inq;
   union {
      POS *a_next;
   } u;
   int pdist;
   POS *bestp, *qp;

   short pmoves;

   short moves, mark, x, y; // May be chars later if space is issue
   int check_qps(POS *b) {
      POS *p = this;
      int bm = p->pmoves;

      while (p != b) {
         if (p->bestp && !isbetw(b->pmoves,p->pmoves,bm)) {
            return 0;
         }
         p = p->qp;
      }
   assert(p->moves == m && p->dist == d);
      return 1;
   }
   void iclear () {
      qbest = MAXDIST;
      moves = 0;
      qp = NULL;
      mark &= ~(MARK_LIMBRANCHED|MARK_INQ);
   }
   INLINE int min_moves_to(POS *p2) {
      int xx=abs(x-p2->x), yy=abs(y-p2->y);
      return max(xx, yy);
   }
   INLINE void lim_clear() {
      assert(mark & MARK_LIMBRANCHED);
      mark &= ~(MARK_LIMBRANCHED);
   }

   INLINE void rsmab(POS *p1, PQ &);
   void recurse_set_moves_and_best(PQ &);
   INLINE void rsm(POS *p1) {
      if ((p1->mark & MARK_LIMBRANCHED) && p1->qp == this) {
         p1->moves = moves+1;
         p1->recurse_set_moves();
      }
   }
   void recurse_set_moves() {
      rsm(this+1);
      rsm(this+1-(MAXSIZE+2));
      rsm(this+1+(MAXSIZE+2));
      rsm(this-1);
      rsm(this-1-(MAXSIZE+2));
      rsm(this-1+(MAXSIZE+2));
      rsm(this-(MAXSIZE+2));
      rsm(this+(MAXSIZE+2));
   }
   INLINE void binbranch(POS *p1, PQ &q, int);
   INLINE void bbranch(PQ &q);
   INLINE void lim_binbranch(POS *p1, PQ &q, int diag);
   INLINE void lim_bbranch(PQ &q);
   INLINE void limax_binbranch(POS *p1, PQ &q);
   INLINE void limax_bbranch(PQ &q);
};

class node_t {
public:
   POS *event;
   node_t *up, *down;


};

class PQ {
public:
   POS root;
   node_t nodes[MAXQELEMS];
   node_t *end, *head;
   int initial;
   void clear();
   void iclear();
   void lim_clear();
   int empty() {
      return end==nodes;
   }
   PQ() {
      node_t *tmp;
      int x;

      initial = 1;
      clear();
      initial = 0;
      for (x=1; x<MAXQELEMS; x++) {
         tmp = nodes+x;
         tmp->up = nodes+(x>>1);
         if ((x<<1) < MAXQELEMS)
            tmp->down = nodes+(x<<1);
         else
            tmp->down = NULL;
      }
   }
   void print();
   void enq(POS *p);
   POS *deq();
   void sift_down();
   void sift_up(node_t *);
};

void PQ :: lim_clear(void)
{
   POS *p;

   if (!initial) {
      while (end != nodes) {
         p = (end--)->event;
         p->inq = NULL;
         p->lim_clear();
      }
   }
   nodes->event = &root;
   head = nodes+1;
   end = nodes;
}

void PQ :: clear(void)
{
   if (!initial) {
      while (end != nodes) {
         (end--)->event->inq = NULL;
      }
   }
   nodes->event = &root;
   head = nodes+1;
   end = nodes;
}

void PQ :: iclear(void)
{
   POS *p;

   if (!initial) {
      while (end != nodes) {
         p = (end--)->event;
         p->inq = NULL;
         p->iclear();
      }
   }
   nodes->event = &root;
   head = nodes+1;
   end = nodes;
}

void PQ :: sift_up(node_t *child)
{
   register best_t insert_priority;
   register POS *u;

   insert_priority = (nodes->event = child->event)->qbest;
   while ((u = child->up->event)->qbest > insert_priority) {
      (child->event = u)->inq = child;
      child = child->up;
      assert(child != NULL);
   }
   (child->event = nodes->event)->inq = child;
}

void PQ :: sift_down(void)
{
   best_t insert_priority;
   node_t *parent, *child;

   parent = head;
   child = parent->down;
   nodes->event = parent->event;
   insert_priority = parent->event->qbest;

   for (;;) {
      assert(child != NULL);
      if (child > end)
         break;
      if (child < end) {
         assert(child+1 < nodes+MAXQELEMS);
         if (child->event->qbest > (child+1)->event->qbest)
            child++;
      }
      if (insert_priority <= child->event->qbest)
         break;
      else {
         (parent->event = child->event)->inq = parent;
         child = (parent = child)->down;
      }
   }
   (parent->event = nodes->event)->inq = parent;
}


void PQ :: enq(POS *event)
{
   if (event->inq) {
      sift_up(event->inq);
   }
   else {
      (++end)->event = event;
      sift_up(end);
   }
   assert(event->inq);
}

POS * PQ :: deq()
{
   POS *e;

   if (nodes < end) {
      e = head->event;
      assert(e->inq);
      head->event = (end--)->event;
      sift_down();
      e->inq = NULL;
      return e;
   }
   return NULL;
}

INLINE void POS :: limax_binbranch(POS *p1, PQ &q) {

      best_t dd = (dist-abs(alt-p1->alt));
      dd /= sqr(moves+1);
      assert(-dd < MAXDIST);
      assert(dd <= 0);
	if ((p1->mark & MARK_OK) && (!(p1->mark & MARK_LIMBRANCHED)
    || (p1->moves >= moves+1 && p1->qbest > dd)) && !p1->bestp) {
      p1->moves = moves+1;
      if ( (p1->mark & MARK_LIMBRANCHED)) {
         /*
         p1->recurse_set_moves();
          */
         p1->recurse_set_moves_and_best(q);
      }
      p1->mark |= MARK_LIMBRANCHED;
      p1->qbest = dd;
      p1->qp = this;

      p1->dist = dist-abs(alt-p1->alt);

      q.enq(p1);
   }
}

/* before calling first instance all POS nodes must have
 * !(mark & MARK_LIMBRANCHED)
 */
INLINE void POS :: limax_bbranch(PQ &q) {
   limax_binbranch(this+1, q);
   limax_binbranch(this+1-(MAXSIZE+2), q);
   limax_binbranch(this+1+(MAXSIZE+2), q);
   limax_binbranch(this-1, q);
   limax_binbranch(this-1-(MAXSIZE+2), q);
   limax_binbranch(this-1+(MAXSIZE+2), q);
   limax_binbranch(this-(MAXSIZE+2), q);
   limax_binbranch(this+(MAXSIZE+2), q);
}

INLINE void POS :: lim_binbranch(POS *p1, PQ &q, int diag)
{
   best_t dd = abs(alt-p1->alt);
   /*
   if ((this->mark & MARK_EDGE) || (p1->mark & MARK_EDGE)) {
      diag *= 2;
   }
    */
   dd = qbest + (dd ? dd*(MAXLIM/2) + diag: diag); /*1*/

   assert(dd < MAXDIST);
   if ((p1->mark & MARK_OK) && (!(p1->mark & MARK_LIMBRANCHED)
    || (p1->moves >= moves+1 && p1->qbest > dd)) && !p1->bestp) {
      p1->moves = moves+1;
      if ( (p1->mark & MARK_LIMBRANCHED)) {
         p1->recurse_set_moves();
      }
      p1->mark |= MARK_LIMBRANCHED;
      p1->qbest = dd;
      p1->qp = this;
      q.enq(p1);
   }
}

/* before calling first instance all POS nodes must have
 * !(mark & MARK_LIMBRANCHED)
 */
INLINE void POS :: lim_bbranch(PQ &q) {
   lim_binbranch(this+1, q, 2);
   lim_binbranch(this+1-(MAXSIZE+2), q, 1);
   lim_binbranch(this+1+(MAXSIZE+2), q, 1);
   lim_binbranch(this-1, q, 2);
   lim_binbranch(this-1-(MAXSIZE+2), q, 1);
   lim_binbranch(this-1+(MAXSIZE+2), q, 1);
   lim_binbranch(this-(MAXSIZE+2), q, 2);
   lim_binbranch(this+(MAXSIZE+2), q, 2);
}

/* would work this way but if B filled up and then you needed to add three
 * then you'd have to add all three to a which would mess up the algorithm
 * if B has the extra space in there it wouldn't happen
#define BHALFMAX ((MAXLEV)/2+1)
#define AHALFMAX ((MAXLEV+1)/2+1)
 */
/* this doesn't work either for larger MAXLEV with the simple algorithm
#define BHALFMAX ((MAXLEV+1)/2+1)
#define AHALFMAX ((MAXLEV+1)/2+1)
 */

class POSMAX {
public:
   int mpdist; /* distance taken by the links so far */
   int maxd;
   POS *a[AHALFMAX], *b[BHALFMAX], **aa, **bb;
   POSMAX() {
      reset();
   }
   void reset() {
      mpdist = maxd = -MAXDIST;
      aa = a;
      bb = b;
   }
   void set(const POSMAX &n) {
      a = n.a;
      b = n.b;
      aa = a+(n.aa-n.a);
      bb = b+(n.bb-n.b);
   }
   POSMAX(const POSMAX &n, int) {
      this->set(n);
   }
   POSMAX(const POSMAX &n) {
      *this = n;
   }
   void add(POS *p) {
      if (bb-b >= aa-a) {
         *aa++ = p;
         assert(aa-a <= AHALFMAX);
      }
      else {
         *bb++ = p;
         assert(bb-b <= BHALFMAX);
      }
   }
   void add(POS *p, POS *p1, POS *p2) {
      if (p != NULL) {
         *aa++ = p;
         assert(aa-a <= AHALFMAX);
      }
      if (p2 != NULL) {
         *bb++ = p2;
         assert(bb-b <= BHALFMAX);
      }
      if (p1 != NULL)
         add(p1);
   }
   void operator = (const POSMAX &n) {
      mpdist = n.mpdist;
      maxd = n.maxd;
      set(n);
   }
   void apply(int , int ) {
      POS **p, *pp;

      for (pp = *a, p = a+1; p != aa; p++) {
         pp->bestp = *p;
         pp = *p;
      }
      for (p = bb; p-- > b; ) {
         pp->bestp = *p;
         pp = *p;
      }
   }
};

class GRID {
public:
   int lim, ht, wd, maxalt, moves, threshold;
   POS *ps, *pend;

   GRID(char *file) {
      FILE *fp = fopen(file, "r");

      bestlong = 0;
      bestshort = 1;
      if (fscanf(fp, "P2\n# %d\n%d %d\n%d\n", &lim, &wd, &ht, &maxalt) != 4) {
         assert(0);
      }
      assert(maxalt <= MAXALT);
      POS *a = ps = (POS*)calloc(sizeof(POS),(MAXSIZE+2)*(MAXSIZE+2));
      for (; a < ps+(MAXSIZE+2)*(MAXSIZE+2); a++) {
         assert(a->alt <= maxalt && a->alt >= 0);
         a->x = ((a-ps)%(MAXSIZE+2))-1;
         a->y = ((a-ps)/(MAXSIZE+2))-1;
         if (a->x<0 || a->y<0 || a->y>=ht || a->x>=wd)
            a->mark &= ~(MARK_OK);
         else {
            /*
            if (a->x==0 || a->y==0 || a->x==ht-1 || a->y==wd-1)
               a->mark |= MARK_EDGE;
                */
            a->mark |= MARK_OK;
            if (fscanf(fp, "%d", &a->alt) != 1) {
               assert(0);
            }
         }
         a->inq = NULL;
         /* calloced
         a->mark = 0;
         a->qp = a->bestp = NULL;
         a->moves = a->dist = 0;
          */
      }
      ps += MAXSIZE+2+1;
      pend = ps + (MAXSIZE+2)*ht - 2 - 1 - (MAXSIZE-wd);
      fclose(fp);
      moves = 0;
      xs = (unsigned char*)malloc(MAXLIM*4);
      ys = xs+MAXLIM*2;

   }
   ~GRID() {
   }

   unsigned char *xs, *ys;
   int bestlong, bestshort, bestmoves, bestsmoves;

   int is_bestdist() {
      int ret;
      /*
      if (bestlong*short_val < long_val*bestshort) {
       */
      if ((float)bestlong*short_val < (float)long_val*bestshort
       && lim >= moves) {
         POS *j = ps;
         unsigned char *xsx = xs, *ysy = ys;
         int m = 0;

         bestlong = long_val;
         bestshort = short_val;
         bestmoves = moves;
         while (j != pend) {
            m++;
            j = j->bestp;
            *xsx++ = j->x;
            *ysy++ = j->y;
         }
         bestsmoves = m;
         while (j != ps) {
            j = j->bestp;
            *xsx++ = j->x;
            *ysy++ = j->y;
         }
         assert(d == bestlong);
         assert(moves == m);
         ret = 1;
      }
      else
         ret = 0;
      return ret;
   }

   void print_bestdist(void) {
      unsigned char *xsx = xs, *ysy = ys;

      while (xsx < xs+bestmoves) {
         printf("%d %d\n", *ysy++, *xsx++);
      }
   }

   /* make the shortest path in moves, either maximizing or minimizing altitude
    * from a to b, where b->...->qp == a, returns if a path was made from
    * a to b.  If PATH_STRICT is set, then the function may not return
    * a path if there is no path at most 'limit' long; if it is not set then
    * the shortest moves path is returned. 
    *
    * best, qp ::: are used and set in each POS
    *
    * Point *1*: if the end was not reached, then there is a block in the middle
    * which we need to get around, so increase the limit and continue on,
    * if there are no more nodes left to enque then there is a problem, you
    * can't get from node a to b.
    *
    * Point *3*: if LIMBRANCHED isn't marked then moves are undefined.
    *
    */
   int make_path(POS *a, POS *b, int path_type, PQ &q, int limit) {

      POS *p, **pp, *pos_head = NULL, *ph, *savebestp = b->bestp;
      int ret;

      b->bestp = NULL;
      assert(q.empty());
      a->moves = 0;
      a->qbest = 0;
      assert(a->mark & MARK_OK);
      a->mark &= ~MARK_OK;
      if (path_type & PATH_MAXIMIZE) {
         a->limax_bbranch(q);
      }
      else {
         a->lim_bbranch(q);
      }
      while (!q.empty()) {
         if (path_type & PATH_MAXIMIZE) {
            while ((p=q.deq())) {
               if (!(p->mark & (MARK_INQ|MARK_OUTQ))) {
                  p->u.a_next = pos_head;
                  pos_head = p;
               }
               if (p == b)
                  break;
               /*FIX: can better do this checking before we enque the branch
                */
               if (((p->mark & MARK_LIMBRANCHED) ? p->moves : 1) /*3*/
                + p->min_moves_to(b) <= limit) {
                  p->limax_bbranch(q);
                  p->mark |= MARK_INQ;
                  p->mark &= ~(MARK_OUTQ);
               }
               else {
                  p->mark |= MARK_OUTQ;
                  assert(!(p->mark & MARK_INQ));
               }
            }
         }
         else {
            while ((p=q.deq())) {
               if (!(p->mark & (MARK_INQ|MARK_OUTQ))) {
                  p->u.a_next = pos_head;
                  pos_head = p;
               }
               if (p == b)
                  break;
               if (((p->mark & MARK_LIMBRANCHED) ? p->moves : 1) /*3*/
                + p->min_moves_to(b) <= limit) {
                  p->lim_bbranch(q);
                  p->mark |= MARK_INQ;
                  /*
                  assert(!(p->mark & MARK_OUTQ));
                   */
                  p->mark &= ~(MARK_OUTQ);
               }
               else {
                  p->mark |= MARK_OUTQ;
                  /*
                  p->mark &= ~(MARK_INQ);
                   */
                  assert(!(p->mark & MARK_INQ));
               }
            }
         }
         if (path_type & PATH_STRICT) {
            break;
         }
         else {
            if (p == b)
               break;
         }
         limit++;
         pp = &pos_head;
         ph = pos_head;
         assert(ph);
         do {
            p = ph->u.a_next;
            if (ph->mark & MARK_OUTQ) {
               ph->u.a_next = NULL;
               assert(!(ph->mark & MARK_INQ));
               assert(ph->mark & MARK_LIMBRANCHED);
               ph->mark &= ~(MARK_OUTQ);
               *pp = p;
               q.enq(ph);
            }
            else
               pp = &ph->u.a_next;
         } while ((ph = p));
      }
      ret = (p == b);
      q.lim_clear();
      for (ph = pos_head; ph; ph = p)  {
         p = ph->u.a_next;
         ph->mark &= ~(MARK_INQ|MARK_OUTQ|MARK_LIMBRANCHED);
      }
      a->mark |= MARK_OK;
      b->bestp = savebestp;
      return ret;
   }

   int short_val, long_val, short_moves;

   POSMAX pms[MAXLEV];

   /* given two points p, p2 and a pivot point p1, check for
    * a maximum pivot at this level and then if level is not limited
    * check for expansion pivot on both two edges of the given pivot
    */
   INLINE void findmax(POS *p, POS *p1, POS *p2, POSMAX &q, const int level) {
      if ((p1->mark & MARK_OK) && !p1->bestp) {
         POSMAX q1(q, 0), q2(q, 0);

         q2.mpdist = abs(p->alt-p1->alt);
         q1.mpdist = abs(p2->alt-p1->alt);
         if (pms[level].maxd < (q.maxd = q.mpdist + q1.mpdist + q2.mpdist)) {
            pms[level] = q;
            pms[level].add(p, p1, p2);
         }
         if (!level)
            return;
         assert(p->bestp == p2);
         p->bestp = p1;
         p1->bestp = p2;
         q2.add(p, NULL, NULL);
         q1.add(NULL, NULL, p2);
         q2.mpdist += q.mpdist;
         q1.mpdist += q.mpdist;
         recurse_pivot(p, q1, level-1);
         recurse_pivot(p1, q2, level-1);
         p->bestp = p2;
         p1->bestp = NULL;
      }
   }

   /* finds maximum possible expansion of the link between p and p->bestp
    * with in the limits of level expansions.
    *
    * return best cost difference in q.maxd and the best pivot q.p
    * if the maximum is to stay put then q.p remains unchanged
    */
   void recurse_pivot(POS *p, POSMAX &q, const int level) {
      POS *p2 = p->bestp;
      int diff = abs(p2-p);

      assert(p2->bestp);
      assert((p->mark & MARK_OK) && (p2->mark & MARK_OK));
      if (diff == 1) {
         findmax(p, p+(MAXSIZE+2), p2, q, level);
         findmax(p, p-(MAXSIZE+2), p2, q, level);
         findmax(p, p2+(MAXSIZE+2), p2, q, level);
         findmax(p, p2-(MAXSIZE+2), p2, q, level);
      }
      else if (diff == (MAXSIZE+2)) {
         findmax(p, p+1, p2, q, level);
         findmax(p, p-1, p2, q, level);
         findmax(p, p2+1, p2, q, level);
         findmax(p, p2-1, p2, q, level);
      }
      else {
         assert(abs(diff - (MAXSIZE+2))==1);
         if (p2 > p) {
            if (p2 == p+1+(MAXSIZE+2)) {
               assert((p[1].mark & MARK_OK) && (p[(MAXSIZE+2)].mark & MARK_OK));
               findmax(p, p+1, p2, q, level);
               findmax(p, p+(MAXSIZE+2), p2, q, level);
            }
            else {
               assert((p[-1].mark & MARK_OK) && (p[(MAXSIZE+2)].mark & MARK_OK));
               assert(p2 == p-1+(MAXSIZE+2));
               findmax(p, p-1, p2, q, level);
               findmax(p, p+(MAXSIZE+2), p2, q, level);
            }
         }
         else {
            assert (p > p2);
            if (p == p2+1+(MAXSIZE+2)) {
               assert((p2[1].mark & MARK_OK) && (p2[(MAXSIZE+2)].mark & MARK_OK));
               findmax(p, p2+1, p2, q, level);
               findmax(p, p2+(MAXSIZE+2), p2, q, level);
            }
            else {
               assert((p2[-1].mark & MARK_OK) && (p2[(MAXSIZE+2)].mark & MARK_OK));
               assert(p == p2-1+(MAXSIZE+2));
               findmax(p, p2-1, p2, q, level);
               findmax(p, p2+(MAXSIZE+2), p2, q, level);
            }
         }
      }
   }

   INLINE void stuff(POS *p, POS *p1, PQ &q, best_t dd) 
   {
      if ((p1->mark & MARK_LIMBRANCHED)) {
         if (p1->moves < p->moves) { /*1*/
            POS *pp;
            for (pp = p; (pp=pp->qp)->moves > p1->moves; )
               assert(pp != ps);
            if (pp == p1)
               return;
         }
      }
      p1->qbest = dd;
      p1->moves = p->moves+1;
      p1->dist = p->dist-abs(p->alt-p1->alt);
      p1->qp = p;
      p1->mark |= MARK_LIMBRANCHED;
      q.enq(p1);
   }

   /* Point *1*: Double check that you're not on same branch
    * Point *2*: also recurse the branch outwards affecting the averages.
    * FIX: cant be put in POS class!!!  maybe if PQ is ok
    */
   INLINE void boiinbranch(POS *p, POS *p1, PQ &q) {

      best_t dd = nu(p->dist-abs(p->alt-p1->alt));
      dd /= de(p->moves+1);
      assert(-dd < MAXDIST);
      assert(dd <= 0);

      if (p1->qbest > dd && !(p1->mark & MARK_SHORTEST) && (p1->mark & MARK_OK)
       && (!(p1->mark & MARK_LIMBRANCHED) || p1->inq || p1->moves >= p->moves) 
       ) {
         stuff(p, p1, q, dd);
      }
   }
   void boiranch(POS *p, PQ &q) {
      boiinbranch(p, p-1-(MAXSIZE+2), q);
      boiinbranch(p, p-(MAXSIZE+2), q);
      boiinbranch(p, p-1, q);
      boiinbranch(p, p+1-(MAXSIZE+2), q);
      boiinbranch(p, p-1+(MAXSIZE+2), q);
      boiinbranch(p, p+1, q);
      boiinbranch(p, p+(MAXSIZE+2), q);
      boiinbranch(p, p+1+(MAXSIZE+2), q);
   }

   /* Point *1*: Double check that you're not on same branch
    * Point *2*: also recurse the branch outwards affecting the averages.
    * FIX: cant be put in POS class!!!  maybe if PQ is ok
    */
   INLINE void boinbranch(POS *p, POS *p1, PQ &q) {

      best_t dd = nu(p->dist-abs(p->alt-p1->alt));
      dd /= de(p->moves+1);
      assert(-dd < MAXDIST);
      assert(dd <= 0);

      if (p1->qbest > dd && !p1->bestp && (p1->mark & MARK_OK)
       /*
       && (!p1->moves || p1->moves > p->moves)) {
        */
       && (!(p1->mark & MARK_LIMBRANCHED) || p1->inq || p1->moves >= p->moves) 
       /*
       && p1->moves+p1->min_moves_to(pend)
       && (ll ? p1->moves+p1->min_moves_to(pend) <= lim : 1)
        */
       ) {
         stuff(p, p1, q, dd);
      }
   }
   void boranch(POS *p, PQ &q) {
      boinbranch(p, p-1-(MAXSIZE+2), q);
      boinbranch(p, p-(MAXSIZE+2), q);
      boinbranch(p, p-1, q);
      boinbranch(p, p+1-(MAXSIZE+2), q);
      boinbranch(p, p-1+(MAXSIZE+2), q);
      boinbranch(p, p+1, q);
      boinbranch(p, p+(MAXSIZE+2), q);
      boinbranch(p, p+1+(MAXSIZE+2), q);
   }

   void longest(PQ &q, int again) {
      POS *p, *j;
      int bestlims = 0, trys = 0;
      POS *lims[MAXLIM*2], **pp;
      double bestlim = 0, minpower = 1.08;
		static double maxpower = 1.9;

      if (again) {
         for (j=pend; j != ps; j=p) {
            p = j->bestp;
            assert(j->bestp);
            j->bestp = NULL;
         }
      }
      do {

         if (trys > bestlims + 8 && bestlims < 2) {
            maxpower = 4;
				minpower = 2;
         }
         if (trys > bestlims + 55)
            break;
         trys++;
         power = RANDFLOAT(minpower,maxpower);
         assert(moves);
         assert(q.empty());
         for (j=ps; j<=pend; j++) {
            assert(j->inq == NULL);
            j->qbest = MAXDIST;
            j->moves = 0;
            j->qp = NULL;
         }
         ps->moves = moves = short_moves;
         pend->bestp = NULL;
         ps->qbest = 0;
         ps->mark |= MARK_LIMBRANCHED;
         for (boranch(ps, q); (p=q.deq()); ) {
            boranch(p, q);
            if (p == pend)
               break;
         }
         for (j=ps; j<=pend; j++)
            j->mark &= ~MARK_LIMBRANCHED;
         q.clear();

         if (p != pend)
            continue;
         
         if (again) {
            moves = short_moves;
            long_val = 0;
            for (j=pend; j != ps; j=p) {
               moves++;
               p = j->qp;
               assert(j->qp);
               long_val += abs(j->alt - j->qp->alt);
               j->bestp = j->qp;
            }
            better_longest(q);
            is_bestdist();
            for (j=pend; j != ps; j=p) {
               p = j->bestp;
               assert(j->bestp);
               j->qp = j->bestp;
               j->bestp = NULL;
            }
         }

         moves = short_moves;

         j = pend;
         long_val = 0;
         pp = lims+MAXLIM;
         *pp = j;
         do {
            *++pp = j->qp;
            long_val += abs(j->alt - j->qp->alt);
         } while (++moves <= lim && (j = j->qp) != ps);

         double t = again ? long_val : (double)long_val/moves;
         if (moves <= lim && bestlim - t < -1e-10) {
            bestlims++;
            bestlim = t;
            pp = lims+MAXLIM;
            pp[-MAXLIM] = *pp;
            while (*++pp != ps) {
               pp[-MAXLIM] = *pp;
            }
            pp[-MAXLIM] = *pp;
         }

      } while (checktime() < (again ? MAXTIME/2+INITTIME : INITTIME));

      if (bestlim) {
         moves = short_moves;
         pp = lims;
         j = pend;
         assert(j == *pp);
         long_val = 0;
         do {
            j->bestp = p = *++pp;
            j->dist = long_val += abs(j->alt - j->bestp->alt);
            j->moves = moves++;
         } while ((j = p) != ps);
      }
      if (!bestlim || moves > lim) {
         int dist;
         if (bestlim) {
            for (p = pend; p != ps; p = j) {
               j = p->bestp;
               p->bestp = NULL;
            }
         }
         dist = make_path(ps, pend, PATH_MAXIMIZE|PATH_STRICT, q,
          (pend->min_moves_to(ps)+(lim-short_moves)+1)/2);
         moves = short_moves;
         dist = 0;
         for (p = pend; p != ps; p = j) {
            p->moves = moves++;
            j = p->bestp = p->qp;
            p->dist = dist += abs(p->alt - j->alt);
         }
         long_val = dist;
         is_bestdist();
      }
   }

   int checktime();
   void better_longest(PQ &) {
      int i, maxd;
      POSMAX *maxpms, pm;
      POS *j;

      for (i = MAXLEV-1; i >= 0; i--) {
         pms[i].reset();
      }
      for (;;) {
         checktime();
         if (lim <= moves)
            break;
         j = pend;
         while (j != ps) { /*1*/
               pm.mpdist = -abs(j->alt-j->bestp->alt);
               recurse_pivot(j, pm, MAXLEV-1);
            j = j->bestp;
         }
         maxd = 0;
         for (i = MAXLEV-1; i >= MAXLEV-min(MAXLEV, lim-moves); i--) {
            if (pms[i].maxd > 0) {
               if (maxd < pms[i].maxd/(MAXLEV-i)) {
                  maxpms = pms+i;
                  maxd = maxpms->maxd/(MAXLEV-i);
               }
            }
         }
         if (!maxd) {
            break;
         }
         maxpms->apply(1+MAXLEV-(maxpms - pms), maxpms->maxd);
         long_val += maxpms->maxd;
         moves += MAXLEV-(maxpms - pms);
         for (i = 0; i < MAXLEV; i++)
            pms[i].reset();
      }
      is_bestdist();
   }

   void count_longest() {
      POS *j;
      int dist = 0;
      int mvs = 0;

      j = pend;
      while (j != ps) {
         dist += abs(j->alt - j->bestp->alt);
         mvs++;
         j = j->bestp;
      }
   }

   void shortest(PQ &);
   void shorten(PQ &q, int a)
   {
      POS *p;
      for (p = ps; p != pend; p++)
         p->bestp = NULL;
      if (!bestshort)
         bestsmoves = pend->min_moves_to(ps);
      make_path(pend, ps, PATH_STRICT, q, a);
      short_val = 0;
      for (moves = 0, p = ps; p != pend; p = p->qp) {
         p->bestp = p->qp;
         short_val += abs(p->alt - p->bestp->alt);
         moves++;
      }
      short_moves = moves;
   }
};

/* Point *1*: in order to minimize 0 altitude moves with out taking one 2 point
 * move over 4 zero altitude moves (using a +1 method) we will each move if the
 * altitude gain is more than zero otherwize 0 altitude moves will be 1.  while
 * minimizes single cots moves it also maximizes diagonal moves, diag = 1 or 2
 * if it not or is a diagonal.
 *
 * Point *2*: also disallows bestps if you want to do a longest before shortest
 */
INLINE void POS :: binbranch(POS *p1, PQ &q, int diag)
{
   best_t dd = abs(alt-p1->alt);
   /*
   if ((this->mark & MARK_EDGE) || (p1->mark & MARK_EDGE)) {
      diag *= 2;
   }
    */
   dd = qbest + (dd ? dd*(MAXLIM/2) + diag: diag); /*1*/

   assert(dd < MAXDIST);
   if (p1->qbest > dd && !p1->bestp && (p1->mark & MARK_OK)) { /*2*/
      p1->qbest = dd;
      p1->qp = this;
      q.enq(p1);
   }
}

/* before calling first instance all POS nodes must have
 * qbest == MAXDIST
 */
INLINE void POS :: bbranch(PQ &q) {
   binbranch(this+1, q, 2);
   binbranch(this+1-(MAXSIZE+2), q, 1);
   binbranch(this+1+(MAXSIZE+2), q, 1);
   binbranch(this-1, q, 2);
   binbranch(this-1-(MAXSIZE+2), q, 1);
   binbranch(this-1+(MAXSIZE+2), q, 1);
   binbranch(this-(MAXSIZE+2), q, 2);
   binbranch(this+(MAXSIZE+2), q, 2);
}

/* use dijiktras algorithm to find shortest path in altitude taking
 * care to also minimize zero altitude moves
 *
 * Point *1*: if the moves left are less than the lowest moves longest
 * back to home then we must draw simple longest path and then draw
 * limited shortest path.
 *
 * Point *2*: or if the longest path back to the start can't be made with
 * in the limit taken by the shortest path, we still do this fix of
 * the shortest path.
 */
void GRID :: shortest(PQ &q) {

   POS *p, *j;
   int dist, save_moves = moves;
   int quick_back_moves = moves ? 0 : ps->min_moves_to(pend);

   for (j=ps; j<=pend; j++) {
      assert(j->inq == NULL);
      j->qbest = MAXDIST;
   }
   assert(q.empty());
   pend->qbest = 0;
   for (pend->bbranch(q); (p=q.deq()); p->bbranch(q)) {
      if (p == ps)
         break;
   }
   if (p != ps) {
      assert(moves);

      /* FIX NEED TO do something if longest blocks shortest */
      assert(0);
   }
   q.clear();

   p->dist = dist = 0;
   while (p != pend) {
      if (ps != p)
         p->mark |= MARK_SHORTEST;
      p->bestp = j = p->qp;
      j->dist = dist += abs(p->alt - j->alt);
      ++moves;
      p = j;
   }
   short_val = dist;

   if (!quick_back_moves) {
      if (moves > lim) {
         make_path(pend, ps, PATH_STRICT, q, lim-quick_back_moves);
         assert(ok); /*FIX:this may not find a path in time as well */

         moves = save_moves;
         p = ps;
         p->dist = dist = 0;
         while (p != pend) {
            if (ps != p)
               p->mark |= MARK_SHORTEST;
            p->bestp = j = p->qp;
            j->dist = dist += abs(p->alt - j->alt);
            ++moves;
            p = j;
         }
         short_val = dist;
         assert(moves <= lim);
      }
   }
   else if ((dist = quick_back_moves+moves-lim) > 0 /*1*/
     || !make_path(ps, pend, PATH_MAXIMIZE, q, quick_back_moves)) { /*2*/
      for (p = ps; p != pend; p = p->qp)
         p->mark &= ~MARK_SHORTEST, p->bestp = NULL;
      make_path(ps, pend, PATH_MAXIMIZE|PATH_STRICT, q, quick_back_moves);
      for (p = pend; p != ps; p = p->qp)
         p->bestp = p->qp;

      make_path(pend, ps, PATH_STRICT, q, lim-quick_back_moves);
      assert(ok);

      p = ps;
      moves = 0;
      p->dist = dist = 0;
      while (p != pend) {
         if (ps != p)
            p->mark |= MARK_SHORTEST;
         p->bestp = j = p->qp;
         j->dist = dist += abs(p->alt - j->alt);
         ++moves;
         p = j;
      }
      short_val = dist;
      save_moves = moves;
      dist = 0;
      for (p = pend; p != ps; p = j) {
         j = p->bestp;
         dist += abs(p->alt - j->alt);
         ++moves;
      }
      long_val = dist;
      better_longest(q);
      is_bestdist();
      for (p = pend; p != ps; p = j) {
         j = p->bestp;
         p->bestp = NULL;
      }
      moves = save_moves;
   }
   short_moves = moves;
}

INLINE void POS :: rsmab(POS *p1, PQ &q) {
   if ((p1->mark & MARK_LIMBRANCHED) && p1->qp == this) {
      p1->dist = dist-abs(alt-p1->alt);
      best_t dd = nu(p1->dist);
      p1->moves = moves+1;
      dd /= de(p1->moves);
      assert(-dd < MAXDIST);
      /*
      assert(p1->qbest >= dd); //FIX this would not need to be >= if used floats
       */
      p1->qbest = dd;

      if (p1->inq)
         q.sift_up(p1->inq);
      p1->recurse_set_moves_and_best(q);
   }
}

void POS :: recurse_set_moves_and_best(PQ &q) {
   rsmab(this+1, q);
   rsmab(this+1-(MAXSIZE+2), q);
   rsmab(this+1+(MAXSIZE+2), q);
   rsmab(this-1, q);
   rsmab(this-1-(MAXSIZE+2), q);
   rsmab(this-1+(MAXSIZE+2), q);
   rsmab(this-(MAXSIZE+2), q);
   rsmab(this+(MAXSIZE+2), q);
}


int GRID::checktime()
{
        int seconds;
        static struct tms TMS;
        times(&TMS);
        /* add the elapsed system and user times                        */
        /* calculation comes out to the nearest second - rounded down   */
        seconds = (TMS.tms_stime + TMS.tms_utime)/CLK_TCK ;

        if (seconds >= MAXTIME)
        {
                is_bestdist();
                print_bestdist();
                /* PRINT OUT YOUR SOLUTION BEFORE YOU GO! */
                exit(0);
        }
        return seconds;
}

int main(int , char *argv[])
{
   GRID grid((argv[1]==NULL) ? "D" : argv[1]);
   PQ q;
   int d;

   d=time(0);
   SRAND(d);

   grid.shortest(q);
   grid.longest(q, 0);
grid.count_longest();
/*
 */
   grid.better_longest(q);
   grid.is_bestdist();
   if (grid.checktime() < MAXTIME/2) {
      grid.longest(q,1);
      grid.shorten(q, max(grid.bestsmoves - 5, grid.pend->min_moves_to(grid.ps)));
      grid.longest(q,0);
      grid.better_longest(q);
      grid.is_bestdist();
      if (grid.checktime() < 2*MAXTIME/3) {
         int t;
         grid.shorten(q, t=(grid.bestsmoves + grid.pend->min_moves_to(grid.ps))/2);
         grid.longest(q,0);
		/*
      grid.improve(q);
		 */

         grid.better_longest(q);
         grid.is_bestdist();
         grid.shorten(q, (t + grid.pend->min_moves_to(grid.ps))/2);
         grid.longest(q,0);
		/*
      grid.improve(q);
		 */

         grid.better_longest(q);
         grid.is_bestdist();
      }
   }
   grid.print_bestdist();
}