#--------- 入力例 ----------
m = 4           # M日後
# (days)日後に、(reward)の報酬を受け取れる仕事
jobs = [{'days':4, 'reward':3},
        {'days':4, 'reward':1},
        {'days':2, 'reward':2}]
#---------------------------
from heapq import heappush, heappop

# days_reward[v]：days[i] = v となる i に対する reward[i] の集合
days_reward = [[] for _ in range(m + 1)]
for job in jobs:
    # 報酬の支払いが M 日を超える場合はパス
    if job['days'] > m:
        pass
    else:
        # データ登録
        days_reward[job['days']].append(job['reward'])

res = 0     # 報酬の最大値
que = []    # ヒープ

# M - 1 日目から 0 日目へとさかのぼる(days_reward[0]から順に見る)
for reward in days_reward:
    for reward1 in reward:
        # ヒープは小さい順となるので符号反転して追加
        heappush(que, reward1 * -1)
    if que:
        x = heappop(que)
        res -= x

print('解：', res)

#--------- 入力例 ----------
x = 3
lst = [2, 2, 2]
#---------------------------
n = len(lst)    # 箱の個数

res = 0         # 解（最小の操作回数）

# 先頭要素のみ x からの超過分を先に減らしておく。
if lst[0] > x:
    res += a[0] - x
    a[0] = x

# 左端から順に処理する
for i in range(n - 1):
    if lst[i] + lst[i + 1] > x:
        res += lst[i] + lst[i + 1] - x
        lst[i + 1] = x - lst[i]
print('【最終の状態（それぞれの箱に入っているキャンディの数）】')
print(lst)
print('------------------')
print('解（操作の最小回数）：', res)

from itertools import combinations_with_replacement
#--------- 入力例 ----------
n, m, q = 3, 4, 3
a = [1, 1, 2]
b = [3, 2, 3]
c = [3, 2, 2]
d = [100, 10, 10]
#---------------------------
# 添字(a, b)を0始まりにする
for i in range(q):
    a[i] -= 1
    b[i] -= 1

# 数列Ａのスコアを算出
def calc_score(A):
    score = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if A[bi] - A [ai] == ci:
            score += di
    return score

res = 0     # 最大値
# 数列Ａを全探索する
for A in combinations_with_replacement(range(1, m + 1), n):
    x = calc_score(A)
    print(A, x)
    res = max(res, x)
print('------------------')
print('解（最大値）：', res)

#--------- 入力例1 ----------
coins = [0.30, 0.60, 0.80]
#--------- 入力例2 ----------
# coins = [0.50]
#--------- 入力例3 ----------
# coins = [0.42, 0.01, 0.42, 0.99, 0.42]
#----------------------------
n = len(coins)      # コインの枚数

# memo[i, j] = i枚目までで表がj回出る確率
memo = {}
memo[0, 0] = 1  # 初期値(表が出る確率100%)

for i in range(1, n + 1):   # コインi枚目
  for j in range(n + 1):    # 表がj回でる確率
    if j == 0:              # 必ず裏になる場合
      memo[i, 0] = memo.get((i - 1, 0), 0) * (1 - coins[i - 1])
    else:                   # [１つ左上の確率に表の出る確率をかけた数値]＋[１つ上の確率に裏の出る確率をかけた数値]
      memo[i, j] = memo.get((i - 1, j - 1), 0) * coins[i - 1] + memo.get((i - 1, j), 0) * (1 - coins[i - 1])

print('【メモ化テーブルの内容】')
for i in range(n + 1):
    for j in range(n + 1):
        print('{:.02f}'.format(memo.get((i, j), 0)), end=' ')
    print()
print()

# 表の個数が裏の個数を上回る確率を合算
print('解：', sum(memo[n, j] for j in range(n//2 + 1, n + 1)))

#--------- 入力例1 ----------
mp = ['...#',
      '.#..',
      '....']
#--------- 入力例2 ----------
# mp = ['..',
#       '#.',
#       '..',
#       '.#',
#       '..']
#--------- 入力例3 ----------
# mp = ['..#..',
#       '.....',
#       '#...#',
#       '.....',
#       '..#..']
#--------- 入力例4 ----------
# mp = ['....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................']
#----------------------------
H, W = len(mp), len(mp[0])
MOD = 10**9 + 7

# メモ化テーブル初期化
memo = [[0] * W for _ in range(H)]
# 初期条件
memo[0][0] = 1

# 全マス目を探索
for i in range(H):
    for j in range(W):
        if i + 1 < H and mp[i + 1][j] == '.':
            memo[i + 1][j] += memo[i][j]    # カウントアップ
            # 計算の途中で余りをとる
            if memo[i + 1][j] >= MOD:
                memo[i + 1][j] -= MOD
        if j + 1 < W and mp[i][j + 1] == '.':
            memo[i][j + 1] += memo[i][j]    # カウントアップ
            # 計算の途中で余りをとる
            if memo[i][j + 1] >= MOD:
                memo[i][j + 1] -= MOD

print('解：', memo[H - 1][W - 1])

#--------- 入力例1 ----------
# ノードの数
n = 4
# 全エッジ（ x → y ）
lst = [(1, 2),
       (1, 3),
       (3, 2),
       (2, 4),
       (3, 4)]
#--------- 入力例2 ----------
# # ノードの数
# n = 6
# # 全エッジ（ x → y ）
# lst = [(2, 3),
#        (4, 5),
#        (5, 6)]
#--------- 入力例3 ----------
# # ノードの数
# n = 5
# # 全エッジ（ x → y ）
# lst = [(5, 3),
#        (2, 3),
#        (2, 4),
#        (5, 2),
#        (5, 1),
#        (1, 4),
#        (4, 3),
#        (1, 3)]
#----------------------------
from collections import defaultdict 

# トポロジーソートを行うクラス
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) 
        self.V = vertices
  
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    def topologicalSortUtil(self, v, visited,stack): 
        visited[v] = True
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        stack.insert(0,v) 
  
    def topologicalSort(self): 
        visited = [False]*self.V 
        stack =[] 
  
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
        return stack

g = Graph(n + 1)    # 0スタートなので頂点を１つ多めに
for a, b in lst:
    g.addEdge(a, b)     # 有向パス追加

print ("トポロジカルソートの結果：", g.topologicalSort())

# トポロジカルソート順に通過数をカウント
memo = {}   # カウント（キー：頂点番号、バリュー：通過数）
for x in list(g.topologicalSort()):
    for a, b in lst:
        if x == a:
            memo[b] = memo.get(a, 0) + 1

print('解：', max(memo.values()))

#---------- 入力例1 ----------
a = 'axyb'
b = 'abyxb'
#---------- 入力例2 ----------
# a = 'aa'
# b = 'xayaz'
#---------- 入力例3 ----------
# a = 'a'
# b = 'z'
#---------- 入力例4 ----------
# a = 'abracadabra'
# b = 'avadakedavra'
#-----------------------------
# メモ化テーブル
memo = {}
x = ''
for i, a1 in enumerate(a):
    for j, b1 in enumerate(b):
        # print(i,j,a1,b1)
        if a1 == b1:
            # print('  #', a1,i,j)
            memo[i + 1, j + 1] = memo.get((i, j), 0) + 1
        else:
            memo[i + 1, j + 1] = max(memo.get((i, j + 1), 0), memo.get((i + 1, j), 0))
print('長さ：', memo[(len(a), len(b))])

# メモ化テーブルの値を見ながら、今いるノード (i,j)(i,j) がどのノードから更新されて来たのかを特定する
i, j = len(a), len(b)

res = ''    # 求める最長の文字列   
while i > 0 and j > 0:
    if memo.get((i, j), 0) == memo.get((i - 1, j), 0):    # (i-1, j) -> (i, j) と更新されていた場合
        i -= 1
    elif memo.get((i, j), 0) == memo.get((i, j - 1), 0):  # (i, j-1) -> (i, j) と更新されていた場合
        j -= 1
    else:                           # (i-1, j-1) -> (i, j) と更新されていた場合
        res = a[i - 1] + res        # 求める文字列を復元する　a[j - 1]でも可
        i -= 1
        j -= 1
print('解：', res)

#--------- 入力例1 ----------
w = 8
items = [{'weight':3, 'value':30},
         {'weight':4, 'value':50},
         {'weight':5, 'value':60}]
#--------- 入力例2 ----------
# w = 5
# items = [{'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000}]
#--------- 入力例3 ----------
# w = 15
# items = [{'weight':6, 'value':5},
#          {'weight':5, 'value':6},
#          {'weight':6, 'value':4},
#          {'weight':6, 'value':6},
#          {'weight':3, 'value':5},
#          {'weight':7, 'value':2}]
#----------------------------
n = len(items)    # 品物の総数

# メモ化テーブル（動的計画法用）
memo = {}

for i, item in enumerate(items):    # 品物ごとにループ
    for j in range(w + 1):          # 重さ＋1までループ
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            # 品物を入れない
            memo[i + 1, j] = memo.get((i, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = memo.get((i, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = memo.get((i, j - items[i]['weight']), 0) + items[i]['value']
            memo[i + 1, j] = max(a, b)    # 価値が高いほうを選択

print('【メモ化テーブルの内容】')
for i, item in enumerate(items):    # 品物ごとにループ
    for j in range(w):              # 重さごとにループ
        print(str(memo[i+1, j+1]).rjust(2, ' '), end=' ')
    print()
print('-----------------------')
print('解（価値の総和の最大値）：', memo[len(items), w])

#--------- 入力例1 ----------
lst = [(10, 40, 70),
       (20, 50, 80),
       (30, 60, 90)]
#--------- 入力例2 ----------
# lst = [(100, 10, 1)]
#--------- 入力例3 ----------
# lst = [(6, 7, 8),
#        (8, 8, 3),
#        (2, 5, 2),
#        (7, 8, 6),
#        (4, 6, 8),
#        (2, 3, 4),
#        (7, 5, 1)]
#----------------------------
n = len(lst)    # 夏休みの日数
# メモ化テーブル（動的計画法用の2次元配列。第１引数：夏休みの日数＋１日、第２引数：３つの活動）
memo = [[0 for i in range(3)] for j in range(n + 1)]

for i in range(n):          # 夏休みの日数分ループ
    for j in range(3):      # 前日の活動 
        for k in range(3):  # 当日の活動
            if j == k:      # 前日と同じ活動はできない
                continue
            # i-1日目(前日)にjの活動、i日目にkの活動を行う場合の幸福度
            memo1 = memo[i][j] + lst[i][k]
            # memo[i + 1][k]はi日目にkを行ったときの得られる累積の最大幸福度
            memo[i + 1][k] = max(memo[i + 1][k], memo1)

for i in range(n + 1):
    print(f'{i}日目の累積最大幸福度', memo[i])
print('解（幸福度の総和の最大値）：',max(memo[n]))

#---------- 入力例 ----------
s = 'erasedream'
#----------------------------
n = len(s)      # 文字列の長さ
memo = [False] * (n + 1)    # メモ化テーブル（動的計画法用の配列）
memo[0] = True

# memo[0]、memo[1]、…、memo[n]を順に求める
for i in range(n + 1):
    if i >= 5 and memo[i - 5] and s[i - 5:i] == 'erase':
        print(i, 'erase')
        memo[i] = True
    if i >= 6 and memo[i - 6] and s[i - 6:i] == 'eraser':
        print(i, 'eraser')
        memo[i] = True
    if i >= 5 and memo[i - 5] and s[i - 5:i] == 'dream':
        print(i, 'dream')
        memo[i] = True
    if i >= 7 and memo[i - 7] and s[i - 7:i] == 'dreamer':
        print(i, 'dreamer')
        memo[i] = True
print('memo', memo)
print('解：Yes' if memo[n] else '解：No')