#!/usr/bin/python

# Christoph Durr, CNRS, 2010 ---- implements the algorithm from
# Polynomial Time Algorithms for Minimum Energy Scheduling with
# Philippe Baptiste, Marek Chrobak, ESA, 136-150, 2007. However this
# implementation does not in time O(n^5), but in O(n^7). The places
# for improvement are the function P, were we tried here to stick
# closest to the recursion of the paper, as well as the function prev,
# which should be precomputed to improve running time.

# Usage: execute with two command line arguments. The first one
# contains release times/processing times/deadlines for all jobs, as
# in "37/8/46 38/2/47 10/5/25" for example and the second contains the
# boot-time L.


from sys  import *
from copy import *

# global variables:
# n = number of jobs
# J = list of jobs
# L = large gap threshold

# -------------------------------------------------------------------- Job
class Job:
    '''a job has release time r, processing time p, deadline d, name
       i. Jobs are ordered according to increasing deadlines. '''

    def __init__(self,r,p,d,i):
        self.r=r
        self.p=p
        self.d=d
        self.i=i

    def __cmp__(self, oth):
        return cmp((self.d,self.r,self.i), (oth.d, oth.r, oth.i))

    def __str__(self):
        return "<job name=%d releasetime=%d processingtime=%d deadline=%d />" \
            % (self.i, self.r, self.p, self.d)
        

def prev(k,t):
    '''maximum rj among jobs j<=k with rj<t. Implementation in O(n), can
       be improved.'''
    r = None   # None = -infinity in python
    for j in range(n):
        rj = J[j].r
        if j<=k and rj<t and rj>r:
            r = rj
    return r



# -------------------------------------------------------------------- Skeleton
class Skeleton:
    '''a skeleton is the support of some schedule. 
       It consists of a non-empty ordered sequence of blocks.
       A block is a pair of the form (starttime,endtime).'''
    
    def __init__(self,b):
       self.b = b

    def __str__(self): return str(self.b)

    def gaps(self):   return len(self.b)-1

    def start(self):  return self.b[0][0]

    def end(self):    return self.b[-1][1]

    def rightFill(self, p):
        '''add support from the end of the skeleton to the right'''
        s,e = self.b[-1]
        self.b[-1] = (s,e+p)

    def leftFill(self, dk, p):
        '''add support from dk to the skeleton to the left, 
        possibly wrapping last blocks.'''
        assert p>0
        previousStart = self.start()
        # create a new last block
        (s1,e1) = (dk-p, dk)
        while len(self.b)>0 and self.end() >= s1:
             (s0,e0) = self.b.pop()
             s1 -= e0-s0
        self.b.append((s1,e1))
        return s1>=previousStart
        
    def __add__(s1,s2):
        '''concatenate two skeletons'''
        assert s1.end()<=s2.start(), "combine overlapping skeletons"
        if s1.end()<s2.start():
            # create a gap
            return Skeleton(s1.b + s2.b)
        else:
            # merge blocks
            assert s1.end()==s2.start()
            merge = (s1.b[-1][0], s2.b[0][1])
            return Skeleton(s1.b[0:-1] + [merge] + s2.b[1:])

# -------------------------------------------------------------------- Schedule

def schedule(sk):
    '''Computes the earliest deadline policy schedule.
       Takes a skeleton and returns sequence of Slots or None, if unfeasible.
       A slot is (s,i,e) where i is scheduled in the interval [s,e).'''
                              # remaining processing times
    p = dict([(i, J[i].p) for i in range(n)])
    S = []                    # the schedule
    if not sk:
       return None
    for (t,endBlock) in sk.b:
        while t<endBlock:
           pending = [i for i in range(n) if p[i]>0 and J[i].r<=t]
           if not pending:
              return None     # no job available
           i = min(pending)   # most urgent pending job
           di = J[i].d
           if di<=t:
              return None     # job expired
                              # next jobs to interrupt i
           moreUrgent = [J[j].r for j in range(i) if p[j]>0 and j!=i]
           Ci = t+p[i]	      # ideal completion time
                              # nextEvent: either completion of i, 
                              # ... or end of block, or interruption
           nextEvent = min(moreUrgent+[Ci, endBlock])
	   S.append((t, i, nextEvent))
           p[i] -= nextEvent-t
           t = nextEvent      # move to next event
                              # verify that all jobs completed
    if [i for i in p if p[i]>0]:
       return None
    return S

def printSchedule(S):
    for (s,i,e) in S:
      if s>=0:                         # don't show dummy job execution
        print "<execution job=%d machine=0 start=%d end=%d />" \
            % (J[i].i, s, e)
        

# -------------------------------------------------------------------- U
UU = {}  # memoization

def U(s,k,g):
    '''Maximal makespan schedule over jobs j<=k with r_j>=r_s and at most
       g gaps.'''
    if (s,k,g) in UU:
        return UU[s,k,g]

    rs = J[s].r
    if k<0:    
        #                                     empty schedule
        UU[s,k,g] = Skeleton([(rs,rs)])
        return UU[s,k,g]

    Usk1g = U(s,k-1,g)
    rk = J[k].r 
    pk = J[k].p
    dk = J[k].d
    #                                         k out of range, or pb unfeasible
    if rk < rs or not Usk1g:
        UU[s,k,g] = Usk1g
        return UU[s,k,g]

    #                                       -- case 0
    if rk > Usk1g.end():
        best = Usk1g
    else:
        best = None # optimal solution

    # we use a single loop so we can interrupt with a single break
    for l,h in [(s,0)]+[(l,h) for l in range(k) for h in range(g+1)]:
        #                                   -- case 1
        p,a = P(s,k,h,l)
        if p>pk:
            continue
        if h<g:
            b = U(l,k-1,g-h-1)
            if b: 
               if p<pk and \
                      dk-b.end()>pk-p and \
                      b.end()>prev(k-1,dk):
                   t = dk-(pk-p)
                   c = a + b
                   if c.leftFill(dk,pk-p):
                      best = c
                      break
        #                                   -- case 2
        b = U(l,k-1,g-h)
        if not b:
           continue
        if p<pk and \
               dk-b.end() <= pk - p and \
               b.end() > prev(k-1,dk):
            c = a + b
            if c.leftFill(dk,pk-p):
                best = c
                break
        #                                   -- case 3
        t = b.end() + pk - p
        if p<=pk and \
            rk <= b.end() and \
            dk - b.end() > pk - p and \
            b.end() > prev(k-1, t+1):    #t+1 for frugality
            c = a + b
            c.rightFill(pk-p)
            if best==None or c.end() > best.end():
                best = c

    UU[s,k,g] = best
    return best
            
# -------------------------------------------------------------------- P
PP = {} # memoization

def P(s,k,g,l):
    '''basically minimal processing time p such that the instance for
       pk<-p has a (s,k)-schedule with makespan r_l. Returns couple
       with this value and the schedule.'''
    if (s,k,g,l) in PP:
        return PP[s,k,g,l]

    rs = J[s].r
    rl = J[l].r
    rk = J[k].r
    pk = J[k].p
    a = U(s,k-1,g)

    if rs>rl or not a:
        PP[s,k,g,l] = ((),None)
        return PP[s,k,g,l]

    if rs==rl or a.end()>=rl:
        PP[s,k,g,l] = (0, Skeleton([(rs,rs)]))
        return PP[s,k,g,l]

    best = ((),None)         # () == +infinity in python

    for h in range(g+1):
        a = U(s,k-1,h)
        if not a:
            continue
        for j in range(k):
            rj = J[j].r
            if rs <= rj and rj <= rl and \
                    prev(k-1,rj) < a.end() and \
                    a.end() < rj and \
                    rk <= a.end():
                p,b = P(j,k,g-h,l)
                if p>pk:
                    continue
                q = rj-a.end()+p
                if q<best[0]:
                    # make a copy of skeleton a
                    r = Skeleton(a.b + [])
                    r.rightFill(rj-r.end())
                    best = (q, r+b)
    PP[s,k,g,l] = best
    #    assert best[1], "found no schedule P"+str((s,k,g,l))
    return best


# -------------------------------------------------------------------- solve

def solve():
    # find first and last release time
    rt = [(J[j].r, -J[j].d, j) for j in range(n)]
    _,_ ,f = min(rt)
    rl,_,_ = max(rt)

    E = {}
    rt.sort()
    rt.reverse()
    # for al jobs s in descending release time order
    for (_,_,s) in rt:
       E[s] = ((),None)
       for g in range(n):
          u = U(s,n-1,g)
          if not u: 
             return ((), None)
          nextRelease = [(J[i].r,i) for i in range(n) if J[i].r>u.end()]
          if not nextRelease:
             alt = (L*g, u)
          else:
             rj,j = min(nextRelease)
             alt = (L*g + rj - u.end() + E[j][0], u+E[j][1])
          if alt<E[s]:
             E[s] = alt
    opt, sk = E[f]
    return (opt, sk)

# -------------------------------------------------------------------- main

assert len(argv)==3, '''argument 2=L, argument 1=space separated jobs, 
                        each job is in the form 
                        releasetime/processingtime/deadline'''


input = map(int, argv[1].replace('/',' ').split())
L     = int(argv[2])
assert  len(input)%3==0, "bad formated input"
n     = len(input)/3

J = []                           # jobs
for i in range(n):
    ri = input[3*i]
    pi = input[3*i+1]
    di = input[3*i+2]
    J.append(Job(ri,pi,di,i))    # job indices start at 0

                                 # add dummy tight job
dummy = Job(-101,1,-100,n)
J.append(dummy)
n+=1
J.sort()           # order with increasing deadlines (inc. r_j to break tie)


opt,sk = solve()
S = schedule(sk)

maxD = max([j.d for j in J])

print "<schedule numberjobs=",n,
print " numbermachines=1",
print " makespan=",            max(10,maxD),
if S:
  print " objvalue=",opt-L," objfct=energy >" # remove dummy job induced cost
  printSchedule(S)
  for i in range(len(sk.b)-1):
    s = sk.b[i][1]
    e = sk.b[i+1][0]
    c = min(e-s,L)
    if s>=0:                                  # remove gap after dummy job
      print "<gap cost=%d machine=0 start=%d end=%d />"%(c,s,e)
else:
  print " objvalue=0 objfct=feasibility >"

for j in J:
    if j!=dummy:
       print str(j)

print "</schedule>"