@Just lsd

В нашем городе работает несколько пунктов обмена валют. Каждый пункт специализируется на обмене двух конкретных валют и выполняет обменные операции только над ними. Может быть несколько пунктов, специализирующихся на обменах одной и той же пары валют. Каждый пункт имеет свой собственный обменный курс. Обменный курс валюты А к валюте В есть количество валюты Bf которое выдается за единицу валюты А. Кроме того, каждый пункт обмена назначает «комиссионные» — сумму, которую вы должны заплатить за операцию обмена. Комиссия всегда собирается в исходной валюте.

Например, если вы хотите обменять 100 долларов США на российские рубли в обменном пункте, в котором курс 29.75, а комиссия 0.39, то вы получите (100 - 0.39) * 29.75 - 2963.3975 российских рублей

Вы точно знаете, что всего есть N различных валют, по которым выполняются обмены в нашем городе — и они обозначаются номерами от 1 до N. Тогда каждый обменный пункт может быть описан 6 числами: целые Л и В — номера валют, с которыми работает данный обменный пункт; и вещественные RAB1 CAB1 RBA и CBA — курсы обмена и комиссионные для обмена валюту А на В и В на А соответственно.

Ввод:
Первая строка входного файла содержит четыре числа: N— количество валют,
М —количество обменных пунктов, 5 —первоначальный номер валюты - уНиколая и V —
первоначальное количество валюты у Николая.
Каждая из последующихМстрок содержит 6 чисел —
описание соответствующего пункта обмена в указанном выше порядке; числа разделены одним или более
пробелами. 1 <S<N< 100, 1 <M< 100, V-действительное число, 0 < V< 1000.
Во всех обменных пунктах «курс» и «комиссия» — вещественные числа, заданные
с двумя знаками после десятичной точки, 0.01 < курс < 100, 0 < комиссия й 100.
Назовем некоторую последовательность обменных операций простой, если в це-
цепочке операций обмена каждый обменный пункт использовался не более одного
раза. Вы можете полагать, что коэффициент отношения сумм в конце и начале
простой последовательности обменных операций будет меньше, чем 10 000.
Вывод:
Если Николай может увеличить свой капитал, выведите «YES», иначе — выведите «NO».


Коротко постановка задачи может быть переформулирована следующим образом:
имеется N видов валют и М пунктов, в которых можно обменивать валюту. Каждый пункт работает с валютами РОВНО двух видов. То есть если он работает с ва-
валютами А и В, то в нем можно поменять валюту А на валюту В и наоборот. Каж-
Каждый валютный пункт задается 6 числами:
А В RAB CAB RBA СВА
Первые два числа (номера видов валют) —
целые, остальные четыре числа —
ве-
вещественные. Обмен VA единиц валюты А на VB единиц валюты В производится
по формуле
VB:-(VA -
CAB)*RAB.
Аналогично обмен VB единиц валюты В на VA единиц валюты А производится по
формуле
VA:-(VB -
CBA)*RBA
Требуется узнать, можно ли увеличить сумму V, заданную в валюте 5, с помощью
имеющейся системы обменных пунктов. При этом обмен каждого типа можно
производить не более одного раза. В условиях оговорено также, что недопустимы
обмены, при которых получается отрицательная сумма.

0