Little Lucy's science project is really giving her a hard time. Her project requires that she build a Rube Goldberg device. A Rube Goldberg device is a device that performs a simple task in a convoluted way. In Lucy's case, she will be performing a series of energy transfers using a variety of parts. Each part will be formatted as "**INPUT OUTPUT TIME**", where INPUT is the type of energy required to start the part, OUTPUT is the type of energy released once the part has done its job, and TIME is the amount of time (in seconds) that the part takes to do its job. Lucy's parts have four different types of energy available: "CHEMICAL", "ELECTRIC", "MECHANICAL", and "THERMAL".

Lucy is going to put several of these devices in series to make a device that will run as close to target seconds as possible. The device will only work if the output from one part can be used as the input to the subsequent part. She can use any type of energy to start her machine, but she must use some part that releases last energy to complete the machine.

Given that Lucy has an infinite supply of each type of part, find the minimum absolute difference between the target time and the time that Lucy's machine operates.

Input

The first line of each test case contains the number of energy transfers n (1 ≤ n ≤ 50), and the values of target and last (1 ≤ target, TIME ≤ 250000). Next n lines describe the tranfers formated as “**INPUT OUTPUT TIME**”.

Output

For each test case print in a separate line the minimum absolute difference between the target time and the time that Lucy's machine operates.