#--------- 入力例 ----------
s = 'AAABBBBBAACDD'
#---------------------------
n = len(s)      # 文字列の長さ
i = 0
while i < n:
    # s[j] != s[i] となる位置を探す
    j = i
    while j < n and s[j] == s[i]:
        j +=  1
    # 文字 s[i] が j - 1 文字連続したことがわかる
    print(s[i], j - i)
    # i を j の位置へ移動
    i = j

#--------- 入力例1 ----------
n,m =4, 7       # じゃんけん数、じゃんけんで出す指の数の合計
s = 'CGPC'      # コンピュータの出すじゃんけんの手
#--------- 入力例2 ----------
# n,m =5, 10      # じゃんけん数、じゃんけんで出す指の数の合計
# s = 'GPCPC'     # コンピュータの出すじゃんけんの手
#---------------------------
cnt_g, cnt_p, cnt_c = 0, 0, 0
for s1 in s:
    if s1 == 'G':
        cnt_g += 1
    elif s1 == 'P':
        cnt_p += 1
    else:
        cnt_c += 1

res = 0
for p in range(m // 5 + 1):   # グーを出せる回数分ループ
    c = (m - p * 5) // 2      # チョキの回数を求める
    g = n - p - c             # グーの回数を求める
    if g < 0:                 # グーの回数がマイナスの場合パス
        pass
    elif p * 5 + c * 2 == m:  # 指の合計本数が指定回数と同じ場合
        x = min(cnt_g, p) + min(cnt_p, c) + min(cnt_c, g)
        res = max(res, x)

print('解：', res)

#--------- 入力例1 ----------
n = 9              # 買いたいミカン数
x, a = 2, 100      # ミカンの個数と金額
y, b = 3, 125      # ミカンの個数と金額
z, c = 5, 200      # ミカンの個数と金額
#--------- 入力例2 ----------
# n = 145            # 買いたいミカン数
# x, a = 12,  752    # ミカンの個数と金額
# y, b = 102, 2483   # ミカンの個数と金額
# z, c = 703, 2810   # ミカンの個数と金額
#---------------------------
# 大きな数値（デフォルト値）
INF = 999999

# メモ化テーブル
memo = {}
memo[0] = 0

for i in range(1, n + z):
    memo[i] = min(memo.get(i, INF), memo.get(i - x, INF) + a)
    memo[i] = min(memo.get(i, INF), memo.get(i - y, INF) + b)
    memo[i] = min(memo.get(i, INF), memo.get(i - z, INF) + c)

print('解：', min(v for k, v in memo.items() if k >= n))

#--------- 入力例 ----------
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)