Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела.
Как известно, количество денег в копилке можно определить, только разбив ее.
Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.
Друг подсказал Васе, что можно оценить минимальное количество денег в копилке,
зная вес пустой копилки и вес копилки с монетами.
Дано E — вес пустой копилки, F — вес копилки с монетами,
N — количество достоинств монет,
Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N).
Требуется определить минимальную сумму, которая может содержаться в копилке.
Формат входного файла
В первой строке входного файла содержатся числа EFN.
В следующих N строках находятся по два числа — CiWi.
Все числа во входном файле — целые.
Формат выходного файла
В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке.
Если заданный вес копилки F не может быть достигнут с монетами заданного типа,
то в выходной файл следует записать число −1.
You are to write a program that finds shortest distances from vertex S
to all other vertices in a given directed weighted graph.
Graph consists of N vertices, numbered from 1 to N, and M edges.
Input file format
Input file contains two integers NMS, followed my M triplets of integers
ui vi wi — starting vertex, ending vertex and weight or the edge.
There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.
Output file format
Output file must contain a vector of N integers — distances from vertex S to other vertices.
The distance from any vertex to itself is considered to be 0.
If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.
Constraints
0 ≤ N, M ≤ 1000.
All weights are less than 1000 by absolute value.
Дана последовательность из N целых чисел. Найдите любую из ее подпоследовательностей,
сумма элементов которой равна w, либо установите,
что искомой подпоследовательности не существует.
Формат входного файла
Во входном файле находятся числа N и w, а за ними следует последовательность
из N целых чисел ai.
Формат выходного файла
Если искомая подпоследовательность существует, выведите N чисел 0 или 1, разделенных пробелами.
Единица на позиции i означает, что элемент последовательности ai принадлежит найденной
подпоследовательности, 0 означает обратное. В противном случае выведите −1.
Скрытая модель Маркова предназначена для описания стохастически эволюционирующих во времени процессов.
Она представляет из себя ориентированный граф состояний, ребрам которого приписаны веса aij,
равные вероятностям перехода из состояния i в j, причем диагональным элементам соответствует вероятность
того, что система останется в том же состоянии.
Кроме того, для каждого состояния известна вероятность bi того, что оно окажется начальным.
Для стороннего наблюдателя состояние не является доступной напрямую информацией — оно скрыто.
Зато он может видеть некоторый производимый системой сигнал, распределение вероятностей которого зависит от состояния.
Таким образом, задание модели завершается указанием матрицы cij — вероятности наблюдать сигнал j при том, что система
находится в состоянии i.
Вторая задача для СММ состоит в том, чтобы по данной модели aijbicij установить последовательность состояний
w1, ..., wk, которая бы являлось наиболее вероятной для данной последовательности сигналов s1, ... , sk.
Напишите программу, которая решает эту задачу.
Формат входного файла
Первая строка входного файла содержит числа N, M, K — количество состояний, уровней сигнала и длину последовательности
наблюдений соответственно.
Вторая строка содержит N чисел bi.
Следующие N строк содержат по N действительных чисел от 0 до 1 и задают матрицу aij, где i — номер строки,
а j — столбца. Сумма элементов каждой строки равна единице.
Следующие N строк содержат по M чисел от 0 до 1 и задают матрицу cij.
Последняя строка содержит K целых чисел от 1 до M и задает последовательность наблюдений si
