#ifndef __GRAPH_H__
#define __GRAPH_H__
 
#include <cassert>
#include <vector>
#include <algorithm>
#include <limits>
#include <queue>
#include <functional>
#include <utility>
#include <stack>
 
/* vector<Edge> とその配列で名前変えたほうがいいかも */
/* 辺の重複、自己ループ、辺の削除(負の辺の判定含め) */
/* 辺の探索 */
/* 経路復元 */
 
using CostType = long long;
 
struct Edge_ToCost {
	int to;
	CostType cost;
	Edge_ToCost(int to, CostType cost);
 
	static int Compare_by_cost(const Edge_ToCost& left, const Edge_ToCost& right);
 
	struct GreaterCost {
		bool operator()(const Edge_ToCost& left, const Edge_ToCost& right);
	};
};
 
struct Edge_FromToCost {
	int from;
	int to;
	CostType cost;
	Edge_FromToCost(int from, int to, CostType cost);
 
	static int Compare_by_cost(const Edge_FromToCost& left, const Edge_FromToCost& right);
 
	struct GreaterCost {
		bool operator()(const Edge_FromToCost& left, const Edge_FromToCost& right);
	};
	struct LessCost {
		bool operator()(const Edge_FromToCost& left, const Edge_FromToCost& right);
	};
};
 
 
/* 多重辺、自己ループはない仕様 */
/* 頂点に何かが割り振られているときもあるよね */
class GraphAsListImpl {
public:
	using Edge = Edge_ToCost;
	using List = std::vector<Edge>;
	using Iterator = List::iterator;
	using ConstIterator = List::const_iterator;
 
protected:
	List* graph_p_m;
	int size_m;
 
	void Copy(const GraphAsListImpl& other);
	bool Is_valid_vertex(int vertex) const;
public:
	GraphAsListImpl();
	GraphAsListImpl(int size);
	GraphAsListImpl(const GraphAsListImpl& other);
	~GraphAsListImpl();
 
	GraphAsListImpl& operator=(const GraphAsListImpl& other);
	const List& operator[](int index) const;
 
	int Size() const;
	void Add(int from, int to, CostType cost, bool bidirected = false);
	Iterator Find(int from, int to);
	ConstIterator Find(int from, int to) const;
	bool Erase(int from, int to);
};
 
class GraphAsListBidirected;
class GraphAsList {
public:
	using Edge = GraphAsListImpl::Edge;
	using List = GraphAsListImpl::List;
	using Iterator = GraphAsListImpl::Iterator;
	using ConstIterator = GraphAsListImpl::ConstIterator;
private:
	GraphAsListImpl graph_impl_m;
public:
	GraphAsList();
	GraphAsList(int size);
	GraphAsList(const GraphAsList& other);
	GraphAsList(const GraphAsListBidirected& other);
	~GraphAsList();
 
	GraphAsList& operator=(const GraphAsList& other);
	const List& operator[](int index) const;
 
	int Size() const;
	void Add(int from, int to, CostType cost = 1, bool bidirected = false);
	Iterator Find(int from, int to);
	ConstIterator Find(int from, int to) const;
	bool Erase(int from, int to, bool bidirected = false);
};
 
 
class GraphAsListBidirected {
public:
	/* メンバ関数に対する friend は記述の順番に注意 */
	friend GraphAsList::GraphAsList(const GraphAsListBidirected& other);
 
	using Edge = GraphAsListImpl::Edge;
	using List = GraphAsListImpl::List;
	using Iterator = GraphAsListImpl::Iterator;
	using ConstIterator = GraphAsListImpl::ConstIterator;
private:
	GraphAsListImpl graph_impl_m;
public:
	GraphAsListBidirected();
	GraphAsListBidirected(int size);
	GraphAsListBidirected(const GraphAsListBidirected& other);
	~GraphAsListBidirected();
 
	GraphAsListBidirected& operator=(const GraphAsListBidirected& other);
	const List& operator[](int index) const;
 
	int Size() const;
	void Add(int vertex1, int vertex2, CostType cost = 1);
	std::pair<Iterator, Iterator> Find(int vertex1, int vertex2);
	std::pair<ConstIterator, ConstIterator> Find(int vertex1, int vertex2) const;
	bool Erase(int vertex1, int vertex2);
};
 
/* 強連結成分分解 */
class SCCsCalculator {
	GraphAsList graph_m;
 
	int current_m;
	std::vector<int> index_m;
	std::vector<int> lowlink_m;
	std::vector<bool> on_stack_m;
	std::stack<int> stack_m;
 
	std::vector<std::vector<int>> SCCs_m;
 
	void Calc_sub_rec(int from);
	void Calc_sub(int start);
 
	static const int UNVISITED = -1;
public:
	SCCsCalculator(const GraphAsList& graph);
	std::vector<std::vector<int>> Calc();
};
 
/* 連結性を仮定 */
class LowlinkCalculator {
public:
	using Edge = Edge_FromToCost;
private:
	GraphAsListBidirected graph_m;
 
	int current_m;
	std::vector<int> index_m;
	std::vector<int> lowlink_m;
	std::vector<int> parent_m;
	//Tree childs;
 
	void Calc_sub_rec(int from, int parent);
	void Calc_sub(int start);
 
	static const int UNVISITED = -1;
public:
	LowlinkCalculator(const GraphAsListBidirected& graph);
	void Calc();
	std::vector<Edge> Bridges();
	std::vector<int> Articulations();
};
 
 
 
struct GraphQueueElement {
	CostType distance_m;
	int vertex_m;
 
	static int Compare(const GraphQueueElement& left, const GraphQueueElement& right);
 
	GraphQueueElement(CostType distance, int vertex);
	GraphQueueElement(const GraphQueueElement&) = default;
};
bool operator<(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator>(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator<=(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator>=(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator==(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator!=(const GraphQueueElement& left, const GraphQueueElement& right);
 
std::vector<CostType> Dijkstra(const GraphAsList& graph, int start);
GraphAsListBidirected Prim(const GraphAsListBidirected& graph_arg);
GraphAsListBidirected Kruskal(const GraphAsListBidirected& graph);
 
#endif
 
#pragma warning(disable:4996)
#if ONLY_MY_ENVIR
#include "Graph.h"
#include "Union_Find.h"
#endif
 
#include <queue>
 
/*-----------------------------------*/
/*---------   Edge_ToCost   ---------*/
/*-----------------------------------*/
 
Edge_ToCost::Edge_ToCost(int to, CostType cost)
	: to(to), cost(cost) {
}
 
int Edge_ToCost::Compare_by_cost(const Edge_ToCost& left, const Edge_ToCost& right) {
	if (left.cost > right.cost) return 1;
	if (left.cost < right.cost) return -1;
	if (left.to > right.to) return 1;
	if (left.to < right.to) return -1;
	return 0;
}
 
bool Edge_ToCost::GreaterCost::operator()(const Edge_ToCost& left, const Edge_ToCost& right) {
	return Compare_by_cost(left, right) > 0;
}
 
/*---------------------------------------*/
/*---------   Edge_FromToCost   ---------*/
/*---------------------------------------*/
 
Edge_FromToCost::Edge_FromToCost(int from, int to, CostType cost)
	:from(from), to(to), cost(cost) {
}
 
int Edge_FromToCost::Compare_by_cost(const Edge_FromToCost & left, const Edge_FromToCost & right) {
	if (left.cost > right.cost) return 1;
	if (left.cost < right.cost) return -1;
	if (left.from > right.from) return 1;
	if (left.from < right.from) return -1;
	if (left.to > right.to) return 1;
	if (left.to < right.to) return -1;
	return 0;
}
 
bool Edge_FromToCost::GreaterCost::operator()(const Edge_FromToCost & left, const Edge_FromToCost & right) {
	return Compare_by_cost(left, right) > 0;
}
 
bool Edge_FromToCost::LessCost::operator()(const Edge_FromToCost & left, const Edge_FromToCost & right) {
	return Compare_by_cost(left, right) < 0;
}
 
 
/*---------------------------------------*/
/*---------   GraphAsListImpl   ---------*/
/*---------------------------------------*/
 
void GraphAsListImpl::Copy(const GraphAsListImpl& other) {
	if (graph_p_m == other.graph_p_m) return;
	delete[] graph_p_m;
	size_m = other.size_m;
	graph_p_m = new List[size_m];
	std::copy(other.graph_p_m, other.graph_p_m + size_m, graph_p_m);
}
 
bool GraphAsListImpl::Is_valid_vertex(int vertex) const {
	return vertex >= 0 && vertex <= size_m;
}
 
GraphAsListImpl::GraphAsListImpl()
	:size_m(0), graph_p_m(nullptr) {
}
 
GraphAsListImpl::GraphAsListImpl(int size)
	: size_m(size) {
	graph_p_m = new List[size_m];
}
 
GraphAsListImpl::GraphAsListImpl(const GraphAsListImpl& other)
	: GraphAsListImpl() {
	Copy(other);
}
 
GraphAsListImpl::~GraphAsListImpl() {
	delete[] graph_p_m;
}
 
GraphAsListImpl& GraphAsListImpl::operator=(const GraphAsListImpl& other) {
	Copy(other);
	return *this;
}
 
const GraphAsListImpl::List& GraphAsListImpl::operator[](int index) const {
	return graph_p_m[index];
}
 
int GraphAsListImpl::Size() const {
	return size_m;
}
 
void GraphAsListImpl::Add(int from, int to, CostType cost, bool bidirected) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	if (bidirected) {
		Add(from, to, cost, false);
		Add(to, from, cost, false);
		return;
	}
	graph_p_m[from].push_back(Edge(to, cost));
}
 
GraphAsListImpl::Iterator GraphAsListImpl::Find(int from, int to) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	for (auto it = list.begin(); it != list.end(); ++it) {
		if (it->to == to) return it;
	}
	return list.end();
}
 
GraphAsListImpl::ConstIterator GraphAsListImpl::Find(int from, int to) const {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	for (auto it = list.begin(); it != list.end(); ++it) {
		if (it->to == to) return it;
	}
	return list.end();
}
 
bool GraphAsListImpl::Erase(int from, int to) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	auto it = Find(from, to);
	if (it == graph_p_m[from].end()) return false;
	list.erase(it);
	return true;
}
 
/*---------------------------*/
/*-----   GraphAsList   -----*/
/*---------------------------*/
 
GraphAsList::GraphAsList() : graph_impl_m() {}
GraphAsList::GraphAsList(int size) : graph_impl_m(size) {}
GraphAsList::GraphAsList(const GraphAsList& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsList::GraphAsList(const GraphAsListBidirected& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsList::~GraphAsList() {}
GraphAsList& GraphAsList::operator=(const GraphAsList& other) {
	graph_impl_m = other.graph_impl_m;
	return *this;
}
 
const GraphAsList::List& GraphAsList::operator[](int index) const {
	return graph_impl_m[index];
}
 
int GraphAsList::Size() const {
	return graph_impl_m.Size();
}
 
void GraphAsList::Add(int from, int to, CostType cost, bool bidirected) {
	graph_impl_m.Add(from, to, cost, bidirected);
}
 
GraphAsList::Iterator GraphAsList::Find(int from, int to) {
	return graph_impl_m.Find(from, to);
}
 
GraphAsList::ConstIterator GraphAsList::Find(int from, int to) const {
	return graph_impl_m.Find(from, to);
}
 
bool GraphAsList::Erase(int from, int to, bool bidirected) {
	if (bidirected) graph_impl_m.Erase(from, to) && graph_impl_m.Erase(to, from);
	return graph_impl_m.Erase(from, to);
}
 
/*-------------------------------------*/
/*-----   GraphAsListBidirected   -----*/
/*-------------------------------------*/
 
GraphAsListBidirected::GraphAsListBidirected() : graph_impl_m() {}
GraphAsListBidirected::GraphAsListBidirected(int size) : graph_impl_m(size) {}
GraphAsListBidirected::GraphAsListBidirected(const GraphAsListBidirected& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsListBidirected::~GraphAsListBidirected() {}
 
GraphAsListBidirected& GraphAsListBidirected::operator=(const GraphAsListBidirected& other) {
	graph_impl_m = other.graph_impl_m;
	return *this;
}
 
const GraphAsListBidirected::List& GraphAsListBidirected::operator[](int index) const {
	return graph_impl_m[index];
}
 
int GraphAsListBidirected::Size() const {
	return graph_impl_m.Size();
}
 
void GraphAsListBidirected::Add(int vertex1, int vertex2, CostType cost) {
	return graph_impl_m.Add(vertex1, vertex2, cost, true);
}
 
std::pair<GraphAsListBidirected::Iterator, GraphAsListBidirected::Iterator>
GraphAsListBidirected::Find(int vertex1, int vertex2) {
	return make_pair(graph_impl_m.Find(vertex1, vertex2), graph_impl_m.Find(vertex2, vertex1));
}
 
std::pair<GraphAsListBidirected::ConstIterator, GraphAsListBidirected::ConstIterator>
GraphAsListBidirected::Find(int vertex1, int vertex2) const {
	return make_pair(graph_impl_m.Find(vertex1, vertex2), graph_impl_m.Find(vertex2, vertex1));
}
 
bool GraphAsListBidirected::Erase(int vertex1, int vertex2) {
	return graph_impl_m.Erase(vertex1, vertex2) && graph_impl_m.Erase(vertex2, vertex1);
}
 
/*--------------------------------------*/
/*---------   SCCsCalculator   ---------*/
/*--------------------------------------*/
 
void SCCsCalculator::Calc_sub_rec(int from) {
	index_m[from] = current_m;
	lowlink_m[from] = current_m;
	++current_m;
	stack_m.push(from);
	on_stack_m[from] = true;
 
	for (auto&& edge : graph_m[from]) {
		int to = edge.to;
		if (index_m[to] == UNVISITED) {
			Calc_sub_rec(to);
			lowlink_m[from] = std::min(lowlink_m[from], lowlink_m[to]);
		} else if (on_stack_m[to]) {		// この条件何のため？
			lowlink_m[from] = std::min(lowlink_m[from], index_m[to]);
		}
	}
 
	if (lowlink_m[from] == index_m[from]) {
		SCCs_m.push_back(std::vector<int>());
		int vertex;
		do {
			vertex = stack_m.top();
			stack_m.pop();
 
			on_stack_m[vertex] = false;
			SCCs_m.back().push_back(vertex);
		} while (vertex != from);
	}
}
 
void SCCsCalculator::Calc_sub(int start) {
	Calc_sub_rec(start);
}
 
SCCsCalculator::SCCsCalculator(const GraphAsList& graph)
	: graph_m(graph), current_m(0), index_m(graph.Size(), UNVISITED),
	lowlink_m(graph.Size(), UNVISITED), on_stack_m(graph.Size(), false) {
}
 
std::vector<std::vector<int>> SCCsCalculator::Calc() {
	const int size = graph_m.Size();
	for (int i = 0; i < size; ++i) {
		if (index_m[i] != UNVISITED) continue;
		Calc_sub(i);
	}
	return SCCs_m;
}
 
/*-----------------------------------------*/
/*---------   LowlinkCalculator   ---------*/
/*-----------------------------------------*/
 
void LowlinkCalculator::Calc_sub_rec(int from, int parent) {
	index_m[from] = current_m;
	lowlink_m[from] = current_m;
	++current_m;
 
	for (auto&& edge : graph_m[from]) {
		int to = edge.to;
		if (to == parent) continue;
 
		if (index_m[to] == UNVISITED) {
			Calc_sub_rec(to, from);
			lowlink_m[from] = std::min(lowlink_m[from], lowlink_m[to]);
			parent_m[to] = from;
		} else {
			lowlink_m[from] = std::min(lowlink_m[from], index_m[to]);
		}
	}
}
 
void LowlinkCalculator::Calc_sub(int start) {
	parent_m[start] = start;
	Calc_sub_rec(start, -1);
}
 
LowlinkCalculator::LowlinkCalculator(const GraphAsListBidirected& graph)
	: graph_m(graph), current_m(0), index_m(graph.Size(), UNVISITED), lowlink_m(graph.Size(), UNVISITED), parent_m(graph.Size()) {
}
 
void LowlinkCalculator::Calc() {
	const int size = graph_m.Size();
	for (int i = 0; i < size; ++i) {
		if (index_m[i] != UNVISITED) continue;
		Calc_sub(i);
	}
}
 
std::vector<LowlinkCalculator::Edge> LowlinkCalculator::Bridges() {
	const int size = graph_m.Size();
	std::vector<Edge> ret_vec;
	for (int i = 0; i < size; ++i) {
		int parent = parent_m[i];
		if (parent == i) continue;
		if (lowlink_m[i] > index_m[parent]) {
			int vertex1 = std::min(i, parent);
			int vertex2 = std::max(i, parent);
			ret_vec.push_back(Edge(vertex1, vertex2, 1));
		}
	}
	return ret_vec;
}
 
std::vector<int> LowlinkCalculator::Articulations() {
	return std::vector<int>();
}
 
 
 
/*----------------------------------*/
/*---------   グローバル   ---------*/
/*----------------------------------*/
 
int GraphQueueElement::Compare(const GraphQueueElement& left, const GraphQueueElement& right) {
	if (left.distance_m > right.distance_m) return 1;
	if (left.distance_m < right.distance_m) return -1;
	return 0;
}
 
GraphQueueElement::GraphQueueElement(CostType distance, int vertex)
	: distance_m(distance), vertex_m(vertex) {
}
 
bool operator<(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) < 0;
}
 
bool operator>(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) > 0;
}
 
bool operator<=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) <= 0;
}
 
bool operator>=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) >= 0;
}
 
bool operator==(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) == 0;
}
 
bool operator!=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) != 0;
}
 
std::vector<CostType> Dijkstra(const GraphAsList& graph, int start) {
	// assert(!Has_negative_edge());
 
	using Elem = GraphQueueElement;
 
	const int size = graph.Size();
	const CostType INF_DIST = std::numeric_limits<CostType>::max();
	std::priority_queue<Elem, std::vector<Elem>, std::greater<Elem> > que;
 
	std::vector<CostType> dist_arr(size, INF_DIST);
	dist_arr[start] = 0;
	que.push(Elem(0, start));
 
	while (!que.empty()) {
		const Elem curr_pair = que.top();
		que.pop();
 
		const CostType curr_dist = curr_pair.distance_m;
		const int from = curr_pair.vertex_m;
 
		if (curr_dist > dist_arr[from]) continue;
 
		for (auto&& elem : graph[from]) {
			const int to = elem.to;
			const CostType cost = elem.cost;
			const CostType new_dist = curr_dist + cost;
 
			if (new_dist >= dist_arr[to]) continue;
			dist_arr[to] = new_dist;
			que.push(Elem(new_dist, to));
		}
	}
	return dist_arr;
}
 
 
/* 無向グラフとみなしてプリム O(ElogE) */
GraphAsListBidirected Prim(const GraphAsListBidirected& graph_arg) {
	using Edge = Edge_FromToCost;
 
	const GraphAsList graph(graph_arg);
	const int size = graph.Size();
	bool* used_p = new bool[size];
	std::fill(used_p, used_p + size, false);
	std::priority_queue<Edge, std::vector<Edge>, Edge::GreaterCost> edge_queue;
	
	int start = 0;
	used_p[start] = true;
	for (auto&& edge : graph[start]) {
		edge_queue.push(Edge(start, edge.to, edge.cost));
	}
 
	int edge_count = 0;
	GraphAsListBidirected ret_graph(size);
	while (edge_count < size - 1) {
		if (edge_queue.empty()) throw std::runtime_error("graph must be connected");
		Edge edge = edge_queue.top(); edge_queue.pop();
		int from = edge.from;
		int to = edge.to;
		CostType cost = edge.cost;
		if (used_p[to]) continue;
 
		used_p[to] = true;
		ret_graph.Add(from, to, cost);
		for (auto&& new_edge : graph[to]) {
			if (used_p[new_edge.to]) continue;
			edge_queue.push(Edge(to, new_edge.to, new_edge.cost));
		}
		++edge_count;
	}
	delete[] used_p;
	return ret_graph;
}
 
/* 無向グラフとみなしてクラスカル O(ElogE) */
GraphAsListBidirected Kruskal(const GraphAsListBidirected& graph) {
#ifdef __UNION_FIND_H__
	using Edge = Edge_FromToCost;
 
	int size = graph.Size();
	UnionFindTree union_find(size);
	std::vector<Edge> edge_arr;
 
	for (int from = 0; from < size; ++from) {
		for (auto&& edge : graph[from]) {
			if (from > edge.to) continue;
			edge_arr.push_back(Edge(from, edge.to, edge.cost));
		}
	}
	std::sort(edge_arr.begin(), edge_arr.end(), Edge::LessCost());
 
	GraphAsListBidirected ret_graph(size);
	int edge_count = 0;
	for(auto&& edge : edge_arr) {
		if (edge_count == size - 1) break;
		int from = edge.from;
		int to = edge.to;
		CostType cost = edge.cost;
		if (union_find.Is_same(from, to)) continue;
		ret_graph.Add(from, to, cost);
		union_find.Unite(from, to);
		++edge_count;
	}
	return ret_graph;
#else
#endif
}
 
#ifndef __FLOW_SOLVER__
#define __FLOW_SOLVER__
 
#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif
 
#include <vector>
#include <algorithm>
#include <limits>
#include <queue>
 
using CapacityType = long long;
struct GraphEdgeWithReverse {
	int to_m;
	CapacityType capacity_m;
	int rev_index_m;		  // グラフの一要素(逆辺の入っている)における逆辺の添字(ポインタにする手もある)
 
	GraphEdgeWithReverse(int to, CapacityType capacity, int rev_index);
};
 
/* 本当は自動的に逆辺の容量を調整するのがよさそう */
class GraphWithReverse {
public:
	typedef GraphEdgeWithReverse Edge;
private:
	std::vector<Edge>* edges_m;
	int size_m;
 
public:
	GraphWithReverse(int size);
	~GraphWithReverse();
 
	int Size() const;
	std::vector<Edge>* Data();
 
	void Add(int from, int to, CapacityType capacity, bool bidirected);
};
 
/* 使い切り */
class FlowSolver {
	static const CapacityType INF_CAPACITY;
	static const int CANNOT_REACH;
private:
	GraphWithReverse graph_m;
 
	CapacityType Ford_fulkerson_sub_rec(int from, int sink, CapacityType curr_max_flow, bool* used_p);
	CapacityType Ford_fulkerson_sub(int source, int sink, bool* used_p);
 
	void Calc_dist(int start, int* dist_p);
	CapacityType Dinic_sub_rec(int from, int sink, CapacityType curr_max_flow, int* done_index_p, int* dist_p);
	CapacityType Dinic_sub(int source, int sink, int* done_index_p, int* dist_p);
public:
	FlowSolver(const GraphAsList& graph_arg);
 
	/* source, sink は頂点番号 */
 
	/* O(E * Maxflow) */
	CapacityType Ford_fulkerson(int source, int sink);
	/* O(E * V ** 2) */
	CapacityType Dinic(int source, int sink);
};
 
 
#endif
 
#ifdef ONLY_MY_ENVIR
#include "Flow_Solver.h"
#endif
 
/*--------------------------------------------*/
/*---------   GraphEdgeWithReverse   ---------*/
/*--------------------------------------------*/
 
GraphEdgeWithReverse::GraphEdgeWithReverse(int to, CapacityType capacity, int rev_index)
	:to_m(to), capacity_m(capacity), rev_index_m(rev_index) {
}
 
GraphWithReverse::GraphWithReverse(int size)
	:size_m(size) {
	edges_m = new std::vector<Edge>[size_m];
}
 
GraphWithReverse::~GraphWithReverse() {
	delete[] edges_m;
}
 
int GraphWithReverse::Size() const {
	return size_m;
}
 
std::vector<GraphWithReverse::Edge>* GraphWithReverse::Data() {
	return edges_m;
}
 
void GraphWithReverse::Add(int from, int to, CapacityType capacity, bool bidirected) {
	if (bidirected) {
		Add(from, to, capacity, false);
		Add(to, from, capacity, false);
		return;
	}
	
	edges_m[from].push_back(Edge(to, capacity, edges_m[to].size()));
	edges_m[to].push_back(Edge(from, 0, edges_m[from].size() - 1));
}
 
/*----------------------------------*/
/*---------   FlowSolver   ---------*/
/*----------------------------------*/
 
const CapacityType FlowSolver::INF_CAPACITY = std::numeric_limits<CapacityType>::max();
const int FlowSolver::CANNOT_REACH = -1;
 
CapacityType FlowSolver::Ford_fulkerson_sub_rec(int from, int sink, CapacityType curr_max_flow, bool* used_p) {
	if (from == sink) return curr_max_flow;
	used_p[from] = true;
 
	typedef std::vector<GraphWithReverse::Edge> GraphDataType;
	GraphDataType* data_p = graph_m.Data();
	for (auto&& edge : data_p[from]) {
		if (used_p[edge.to_m] || edge.capacity_m <= 0) continue;
		CapacityType flow = Ford_fulkerson_sub_rec(edge.to_m, sink, std::min(curr_max_flow, edge.capacity_m), used_p);
		if (flow > 0) {
			edge.capacity_m -= flow;
			data_p[edge.to_m][edge.rev_index_m].capacity_m += flow;
			return flow;
		}
	}
	return 0;
}
 
CapacityType FlowSolver::Ford_fulkerson_sub(int source, int sink, bool* used_p) {
	const int size = graph_m.Size();
	std::fill(used_p, used_p + size, false);
	return Ford_fulkerson_sub_rec(source, sink, INF_CAPACITY, used_p);
}
 
void FlowSolver::Calc_dist(int start, int* dist_p) {
	typedef std::vector<GraphWithReverse::Edge> GraphDataType;
	const int size = graph_m.Size();
	std::fill(dist_p, dist_p + size, CANNOT_REACH);
	GraphDataType* data_p = graph_m.Data();
 
	std::queue<int> dist_queue;
	dist_p[start] = 0;
	dist_queue.push(start);
	while (!dist_queue.empty()) {
		int from = dist_queue.front(); dist_queue.pop();
		for (auto&& edge : data_p[from]) {
			if (dist_p[edge.to_m] != CANNOT_REACH || edge.capacity_m <= 0) continue;
			dist_p[edge.to_m] = dist_p[from] + 1;
			dist_queue.push(edge.to_m);
		}
	}
}
 
CapacityType FlowSolver::Dinic_sub_rec(int from, int sink, CapacityType curr_max_flow, int* done_index_p, int* dist_p) {
	if (from == sink) return curr_max_flow;
 
	typedef std::vector<GraphWithReverse::Edge> GraphDataType;
	GraphDataType* data_p = graph_m.Data();
	for (int& i = done_index_p[from]; i < data_p[from].size(); ++i) {		// i は done_index_p[from] の別名
		GraphWithReverse::Edge& edge = data_p[from][i];
		if (dist_p[edge.to_m] <= dist_p[from] || edge.capacity_m <= 0) continue;
		CapacityType flow = Dinic_sub_rec(edge.to_m, sink, std::min(curr_max_flow, edge.capacity_m), done_index_p, dist_p);
		if (flow > 0) {
			edge.capacity_m -= flow;
			data_p[edge.to_m][edge.rev_index_m].capacity_m += flow;
			return flow;
		}
	}
	return 0;
}
 
CapacityType FlowSolver::Dinic_sub(int source, int sink, int* done_index_p, int* dist_p) {
	return Dinic_sub_rec(source, sink, INF_CAPACITY, done_index_p, dist_p);
}
 
FlowSolver::FlowSolver(const GraphAsList& graph_arg)
	: graph_m(graph_arg.Size()) {
	const int size = graph_arg.Size();
 
	for (int from = 0; from < size; ++from) {
		for (auto&& edge : graph_arg[from]) {
			graph_m.Add(from, edge.to, edge.cost, false);
		}
	}
}
 
CapacityType FlowSolver::Ford_fulkerson(int source, int sink) {
	const int size = graph_m.Size();
	bool* used_p = new bool[size];
	std::fill(used_p, used_p + size, false);
 
	CapacityType sum_flow = 0;
	while (true) {
		CapacityType curr_flow = Ford_fulkerson_sub(source, sink, used_p);
		if (curr_flow == 0) break;
		sum_flow += curr_flow;
	}
 
	delete[] used_p;
	return sum_flow;
}
 
CapacityType FlowSolver::Dinic(int source, int sink) {
	const int size = graph_m.Size();
	int* done_index_p = new int[size];
	int* dist_p = new int[size];
 
	CapacityType sum_flow = 0;
	while (true) {
		Calc_dist(source, dist_p);
		if (dist_p[sink] == CANNOT_REACH) break;
		std::fill(done_index_p, done_index_p + size, 0);
		while (true) {
			CapacityType curr_flow = Dinic_sub(source, sink, done_index_p, dist_p);
			if (curr_flow == 0) break;
			sum_flow += curr_flow;
		}
	}
 
	delete[] done_index_p;
	delete[] dist_p;
	return sum_flow;
}
 
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
 
using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i,a,n) for(LL i = (a); i < (LL)(n); ++i)
#define REM(i,a,n) for(LL i = ((n) - 1); i >= (a); --i)
#define FLOAT setprecision(16)
#define IGNORE
#define SPEEDUP {cin.tie(0); ios::sync_with_stdio(false);}
#define INSIDE(i,j,H,W) ((i) >= 0 && (i) < (H) && (j) >= 0 && (j) < (W))
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const string INFSTR = "\x7f";
const double EPS = 1.0e-9;
 
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(begin(dest), end(dest), val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template<class T>
T Compare(T left, T right) { return left > right ? 1 : (left < right ? -1 : 0); }
istream& Ignore(istream& ist) {string s; ist >> s; return ist;}
 
// all_of
// partial_sum, adjacent_difference
 
#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "Union_Find.h"
#include "Graph.h"
#include "Range.h"
#include "Global.h"
#include "Flow_Solver.h"
#include "Tree.h"
#include "Suffix_Array.h"
#include "Geometry.h"
#endif
 
#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp;  ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif
 
#if 1234567891
#include <array>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;	// コスト小を優先
#endif
 
int N;
LL A[101];
			
int main() {
	cin >> N;
	LL ans = 0;
	REP(i, 1, N + 1) {
		cin >> A[i];
	}
	GraphAsList G(N + 2);
	REP(i, 1, N + 1) {
		if (A[i] < 0) G.Add(0, i, -A[i]);
		if (A[i] > 0) {
			G.Add(i, N + 1, A[i]); ans += A[i];
		}
		for (int j = 2 * i; j <= N; j += i) {
			G.Add(i, j, INFLL);
		}
	}
	FlowSolver F(G);
	ans -= F.Dinic(0, N + 1);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256