def compare(a : str, b : str) -> str:
if a == '' and b == '':
   return '='
elif a == '' and b != '':
   return '<'
elif a != '' and b == '':
   return '>'
else:
   if a[0] < b[0]:
         return '<'
   elif a[0] > b[0]:
         return '>'
   else:
         return compare(a[1:], b[1:])

def is_sorted(l : list) -> bool:
if len(l) == 0 or len(l) == 1:
   return True
else:
   if l[0] > l[1]:
         return False
   else:
         return is_sorted(l[1:])

def merge (l1 : list, l2 : list) -> list:
if l1 == [] or l2 == []:
   return l1 + l2
else:
   if l1[0] <= l2[0]:
         return [l1[0]] + merge(l1[1:], l2)
   else:
         return [l2[0]] + merge(l1, l2[1:])

def sort(l : list) -> list:
if len(l) == 0 or len(l) == 1:
   return list(l)
else:
   return merge(sort(l[:len(l) // 2]), sort(l[len(l) // 2:]))

def max_value(gifts : ((int,int),) , weight_limit : int) -> int:
w, v = gifts[0]
if len(gifts) == 1:
   if w > weight_limit:
         return 0
   else:
         return v
else:
   if w > weight_limit:
         return max_value(gifts[1:], weight_limit)
   else:
         return max((v + max_value(gifts[1:], weight_limit-w)), (max_value(gifts[1:], weight_limit)))

if __name__=="__main__":
import random

APT: CG ratio Problem Statement Specification Regions of a DNA g...