denotes number of ways of putting people in groups of size . where denotes number of ways to distribute people in groups of size .

.
Answer is .

First observation : a solution will visit a range of restaurants, pick the best meal for each ticket in the range, and pay the distance from the start to the end of the range.

It is possible to compute the optimal solution for a range in O(m) time using m range maximum queries and subtracting the distance. This gives a O(n^2 m) algorithm. It is possible to improve it to O(m n log(n)) with divide and conquer optimization.

Code for D&D optimization :

// compute optimal values for ranges starting in [l..r-1], ending in [optL..optR]
void calc(int l, int r, int optL, int optR){
  int mi = (l+r)/2;
  // find the optimal range starting at mi
  int optM=optL; int curval=0;
  FORU(k, max(mi,optL), n-1) {
    // compute the value of the range [mi..k]
    int val = computeValue(mi,k);
    if(val > curval) { curval = val; optM = k; }
  }
  // the optimal end for mi is optM
  ans = max(ans, curval);
  if(l<r-1) {
    calc(l,mi,optL,optM);
    calc(mi,r,optM,optR);
  }
}

calc(0,n,0,n-1);

Let's for each pair (restaurant; ticket number) find all segments of restaurants, on which this pair will be used. To do so we can use standard algorithm with stack, to find nearest restaurants with better meals for this tickets. Let's call position of our restaurant pos, and these two restaurants rightPos and leftPos. Our pair will be used on segments with left border [leftPos + 1;pos], and right position [pos;rightPos - 1]. To find values for each segment we can just add value of all pairs in correspounding rectangles in [leftPos;rightPos] plane. It will work in O(n² + nm)