YES
Input TRS:
      1: app(nil(),k) -> k
      2: app(l,nil()) -> l
      3: app(cons(x,l),k) -> cons(x,app(l,k))
      4: sum(cons(x,nil())) -> cons(x,nil())
      5: sum(cons(x,cons(y,l))) -> sum(cons(a(x,y,h()),l))
      6: a(h(),h(),x) -> s(x)
      7: a(x,s(y),h()) -> a(x,y,s(h()))
      8: a(x,s(y),s(z)) -> a(x,y,a(x,s(y),z))
      9: a(s(x),h(),z) -> a(x,z,z)
Number of strict rules: 9
Direct POLO(bPol) ... failed.
Uncurrying sum
      1: app(nil(),k) -> k
      2: app(l,nil()) -> l
      3: app(cons(x,l),k) -> cons(x,app(l,k))
      4: sum^1_cons(x,nil()) -> cons(x,nil())
      5: sum^1_cons(x,cons(y,l)) -> sum^1_cons(a(x,y,h()),l)
      6: a(h(),h(),x) -> s(x)
      7: a(x,s(y),h()) -> a(x,y,s(h()))
      8: a(x,s(y),s(z)) -> a(x,y,a(x,s(y),z))
      9: a(s(x),h(),z) -> a(x,z,z)
      10: sum(cons(_1,_2)) ->= sum^1_cons(_1,_2)
Number of strict rules: 9
Direct POLO(bPol) ... failed.
Dependency Pairs:
     #1: #a(s(x),h(),z) -> #a(x,z,z)
     #2: #a(x,s(y),h()) -> #a(x,y,s(h()))
     #3: #sum(cons(_1,_2)) ->? #sum^1_cons(_1,_2)
     #4: #sum^1_cons(x,cons(y,l)) -> #sum^1_cons(a(x,y,h()),l)
     #5: #sum^1_cons(x,cons(y,l)) -> #a(x,y,h())
     #6: #app(cons(x,l),k) -> #app(l,k)
     #7: #a(x,s(y),s(z)) -> #a(x,y,a(x,s(y),z))
     #8: #a(x,s(y),s(z)) -> #a(x,s(y),z)
Number of SCCs: 3, DPs: 6
  SCC { #6 }
POLO(Sum)... succeeded.
      a 	w: 0
      h 	w: 0
      s 	w: 0
      sum^1_cons	w: 0
      sum	w: 0
      nil	w: 0
      #sum^1_cons	w: 0
      #app	w: x1
      cons	w: x2 + 1
      #a 	w: 0
      #sum	w: 0
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #6
Number of SCCs: 2, DPs: 5
  SCC { #4 }
POLO(Sum)... succeeded.
      a 	w: x1 + x2 + 1
      h 	w: 1
      s 	w: x1 + 4
      sum^1_cons	w: 0
      sum	w: 0
      nil	w: 0
      #sum^1_cons	w: x2
      #app	w: 0
      cons	w: x1 + x2 + 1
      #a 	w: 0
      #sum	w: 0
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #4
Number of SCCs: 1, DPs: 4
  SCC { #1 #2 #7 #8 }
POLO(Sum)... succeeded.
      a 	w: x1 + x2 + 1
      h 	w: 1
      s 	w: x1 + 4
      sum^1_cons	w: 0
      sum	w: 0
      nil	w: 0
      #sum^1_cons	w: 0
      #app	w: 0
      cons	w: 1
      #a 	w: x1
      #sum	w: 0
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #1
Number of SCCs: 1, DPs: 3
  SCC { #2 #7 #8 }
POLO(Sum)... succeeded.
      a 	w: x1 + x2 + 1
      h 	w: 1
      s 	w: x1 + 4
      sum^1_cons	w: 0
      sum	w: 0
      nil	w: 0
      #sum^1_cons	w: 0
      #app	w: 0
      cons	w: 1
      #a 	w: x2
      #sum	w: 0
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #2 #7
Number of SCCs: 1, DPs: 1
  SCC { #8 }
POLO(Sum)... POLO(max)... succeeded.
      a 	w: 0
      h 	w: 0
      s 	w: x1 + 1
      sum^1_cons	w: 0
      sum	w: 0
      nil	w: 0
      #sum^1_cons	w: 0
      #app	w: 0
      cons	w: 0
      #a 	w: max(x3 + 1)
      #sum	w: 0
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #8
Number of SCCs: 0, DPs: 0