Dynamic Graph Programming

ID 38135. Routing schemes

Error

ID 38303. Gourmet's Choice

Error

ID 38444. villages

There are N villages in the thirtieth state. Some pairs of villages are connected by roads. In order to save money, “superfluous” there are no roads, i.e. There is only one way to get from any village to any village by road.
The latest research has shown that the thirtieth state is located in a seismically dangerous zone. Therefore, the head of state wanted to know what kind of damage an earthquake could bring to his country. Namely, he wants to know what is the minimum number of roads that must be destroyed in order to form a group of exactly P villages, isolated from the rest, such that from any village from this group to any other village from this group it will still be possible to get by undestroyed roads (a group is isolated from the rest if no undamaged road connects a village in this group with a village not in this group).
You should write a program to help him with this.

Input data format
The first line of the input file contains two numbers: N and P (1 ≤ P ≤ N ≤ 150). All other lines contain road descriptions, one per line: the road description consists of two village numbers (from 1 to N) that this road connects. All numbers in the input file are separated by spaces and/or newlines.

Output data format
In the output file print a single number — desired number of roads.

Examples

ID 40125. Shortcut to DAG

A directed weighted acyclic graph is given. It is required to find the shortest path in it
from vertex s to vertex t.

Input:
The first line of the input file contains four integers n, m, s and t - the number of vertices, edges of the graph, the initial and final vertices, respectively (1 <= n <= 100000; 0 <= m <= 200000; 1 < ;= s, t <= n).
The next m lines contain the descriptions of the edges, one per line. 
Edge number i is described by three integers b_i, e_i and w_i - the beginning, end and length of the edge, respectively (1 <= b _i, e_i <= n;|w_i| <= 1000). 
The graph does not contain cycles and loops.

Output:
The first line of the output file must contain a single integer - the length of the shortest path from s to t. 
If there is no path from s to t, print "Unreachable".

Examples:
 

ID 40126. substring path

Given a graph of n vertices and m directed edges. Each vertex contains some lowercase Latin letter. 
Let's define the length of a path as the largest number of times that some letter was encountered along this path. For example, if the letters in the path form the string "abaca", then the value of this path is 3.
Your task — find the path with the largest value.

Input:
The first line contains two integers n, m (1 ≤ n, m ≤ 200000), meaning that the graph has n vertices and m directed edges.
The second line contains the string s, consisting only of lowercase Latin letters. Symbol number i — this is the letter written at the top number i.
Then m lines follow. Each of these lines contains two integers x, y (1 ≤ x, y ≤ n) describing a directed edge from x to y. Note that x can be equal to y, and there can be multiple edges between x and y.
In addition, the graph may be disconnected.

Output:
Print one number — the maximum path length. If there are paths with an arbitrarily large value, print -1.

Examples:
 

ID 40127. En and mushrooms

En goes to her Mushroom Forest to gather mushrooms.

There are m oriented paths in the Mushroom Forest connecting n trees. Mushrooms grow on every path. When En walks along a path, he picks up all the mushrooms on that path. However, the Mushroom Forest has such fertile soil that mushrooms grow at a fantastic rate. New mushrooms grow as soon as En finishes picking mushrooms on the path. Namely, after En passes along the path for the i-th time, grows i fewer mushrooms than it was before this passage. Thus, if the path initially had x mushrooms, then En will collect x mushrooms in the first pass, x - 1 mushroom in the second, x - 1 - 2 mushrooms in the third, and so on. However, the number of mushrooms cannot become less than 0.
For example, let initially 9 mushrooms grow on the path. Then the number of mushrooms that En will collect is 9, 8, 6, and 3 for passes one through four. From the fifth pass onwards, En won't be able to collect anything from this path (but can still walk on it).

En decided to start from tree s. What is the maximum number of mushrooms he can collect by moving only along the described paths?

Input:
The first line contains two integers n and m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — the number of trees and the number of oriented paths in the Mushroom Forest, respectively.
Each of the next m lines contains three integers x, y and w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10⁸ ) describing a path that leads from tree x to tree y with w mushrooms initially. There are paths that lead from a tree to the same tree, as well as several paths connecting the same pair of trees.
The last line contains a single integer s (1 ≤ s ≤ n) — En's starting position.

Output:
Print a single integer — The maximum number of mushrooms that En can collect on her way.

Examples:
 

ID 40166. Lottery

On one of the TV channels, the next lottery is held every week. During the week, participants make their bets. Each bet consists of naming some M-digit number in the base K number system (that is, in fact, each participant names M digits, each of which lies in the range from 0 to K & minus; 1). Leading zeros are allowed in numbers.

At some point, betting on the current draw ends, and after that, the presenter announces the winning number on television (this is also an M-digit number in the K-ary number system). After that, those TV viewers, whose first digit of their number coincided with the first digit of the number named by the host, receive a win in the amount of A₁ rubles. Those who matched the first two digits of — receive A₂ rubles (at the same time, if the player has the second digit matched, but the first digit did not match, he does not receive anything). Similarly, those who guessed the first three digits receive A₃ rubles. And so on. Those who guessed the whole number fully receive Am rubles. Moreover, if the player guessed the first t digits, then he receives A_t rubles, but does not receive prizes for guessing t−1, t−2, etc. digits. If the player didn't guess the first number, he gets nothing.

Write a program that, given the known bets made by viewers, finds the number that the TV presenter must name in order for the organizing company to pay out the minimum amount as winnings. For your convenience, bets made by players are already sorted in non-descending order.

Input
The first line contains the numbers N (the number of TV viewers who made their bets, 1N100000), M (the length of the numbers 1M10) K (the base of the number system 2 ≤ K ≤ 10). The next line contains M integers A₁, A₂, ..., A_M, specifying payoffs if only the first, first two ,... , all digits (1 ≤ A₁ ≤ A₂ ≤ ... ≤ A_M ≤ 100000 ). Each of the next N lines contains one M-digit K-ary number. The numbers are in non-decreasing order.

Imprint
On the first line print the desired number (if there are several solutions — print any of them), and on the second line — the amount that, when naming the TV presenter on the first day, will have to be paid as a win.

Examples