LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）D,F,G問題メモ

n, l, r = map(int, input().split())
aaa = list(map(int, input().split()))

dp1 = 0
dp2 = 0
dp3 = 0
for a in aaa:
    ndp1 = dp1 + l
    ndp2 = min(dp1, dp2) + a
    ndp3 = min(dp1, dp2, dp3) + r
    dp1 = ndp1
    dp2 = ndp2
    dp3 = ndp3

ans = min(dp1, dp2, dp3)
print(ans)

n = int(input())
ccc = [list(map(int, input().split())) for _ in range(1 << n)]
ccc = list(map(list, zip(*ccc)))

ans = 0
for i in range(n):
    b = 1 << (i + 1)
    for j in range(0, 1 << n, b):
        cur = max(ccc[i][j:j + b])
        ans += cur
        for k in range(i + 1, n):
            for l in range(j, j + b):
                ccc[k][l] -= cur

print(ans)

from collections import deque
from typing import List, Tuple


class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """

    def __init__(self, n: int):
        self.n = n
        self.links: List[List[List[int]]] = [[] for _ in range(n)]
        # if exists an edge (v→u, capacity)...
        #   links[v] = [ [ capacity, u, index of rev-edge in links[u], is_original_edge ], ]

    def add_link(self, from_: int, to: int, capacity: int) -> None:
        self.links[from_].append([capacity, to, len(self.links[to]), 1])
        self.links[to].append([0, from_, len(self.links[from_]) - 1, 0])

    def bfs(self, s: int) -> List[int]:
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        return depth

    def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
        links = self.links
        stack = [s]

        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                cap, to, rev, _ = links[v][i]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0

        f = 1 << 60
        fwd_links = []
        bwd_links = []
        for v in stack[:-1]:
            cap, to, rev, _ = link = links[v][progress[v]]
            f = min(f, cap)
            fwd_links.append(link)
            bwd_links.append(links[to][rev])

        for link in fwd_links:
            link[0] -= f

        for link in bwd_links:
            link[0] += f

        return f

    def max_flow(self, s: int, t: int) -> int:
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow

    def cut_edges(self, s: int) -> List[Tuple[int, int]]:
        """ max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
        q = [s]
        reachable = [0] * self.n
        reachable[s] = 1
        while q:
            v = q.pop()
            for cap, u, li, _ in self.links[v]:
                if cap == 0 or reachable[u]:
                    continue
                reachable[u] = 1
                q.append(u)
        edges = []
        for v in range(self.n):
            if reachable[v] == 0:
                continue
            for cap, u, li, orig in self.links[v]:
                if orig == 1 and reachable[u] == 0:
                    edges.append((v, u))
        return edges


def get_spf(n):
    """ nまでの各数を割り切る一番小さな素数 """
    spf = list(range(n + 1))
    for i in range(2, n + 1, 2):
        spf[i] = 2
    for p in range(3, int(n ** 0.5) + 1, 2):
        if spf[p] == p:
            for m in range(p * p, n + 1, 2 * p):
                if spf[m] == m:
                    spf[m] = p
    return spf


n = int(input())
s = 2 * n
t = s + 1
max_flow = Dinic(2 * n + 2)

spf = get_spf(20_000_000)
INF = 1 << 60

numbers = [tuple(map(int, input().split())) for _ in range(n)]
for i in range(n):
    a1, b1 = numbers[i]
    max_flow.add_link(s, i, b1)
    max_flow.add_link(n + i, t, b1)

    if a1 == 1:
        max_flow.add_link(i, n + i, INF)

    for j in range(i + 1, n):
        a2, b2 = numbers[j]
        p = a1 + a2
        if spf[p] == p:
            max_flow.add_link(i, n + j, INF)
            max_flow.add_link(j, n + i, INF)

ans = max_flow.max_flow(s, t)

print(ans // 2)