Mushroom Harvest in ESQMS Forest

Little Pang and ZYR are going to gather mushrooms in the magical ESQMS forest. In the forest there are \(N\) bushes and \(M\) directed paths. Each path connects two bushes and has an initial number of mushrooms. When a path is traversed once, all mushrooms on that path are collected and then the mushrooms regrow. The new number of mushrooms becomes the product of the original number and the path's recovery coefficient, rounded down, i.e.

[ \text{new} = \lfloor \text{old} \times c \rfloor ]

For example, if a path initially has 4 mushrooms and its recovery coefficient is 0.7, the amounts collected on the 1st to 4th traversals will be 4, 2, 1, 0 respectively.

Starting from bush \(S\), Little Pang and ZYR can traverse paths arbitrarily (possibly reusing paths) and collect mushrooms. Determine the maximum number of mushrooms they can collect.

Note: Each path can be used repeatedly. The available mushrooms on a path are determined by the number of times it has been traversed before; after each traverse, the mushrooms on that path update to \(\lfloor\text{current}\times c\rfloor\). It is guaranteed that the number of mushrooms on every path will eventually drop to zero.

inputFormat

The first line contains three numbers: \(N\), \(M\) and \(S\) \( (1 \le S \le N)\), where \(N\) is the number of bushes and \(M\) is the number of directed paths.

Each of the following \(M\) lines contains four values: u v A c, where:

• u and v (1-based indices) denote a directed path from bush u to bush v,
• A (an integer) is the initial number of mushrooms on that path,
• c (a floating-point number) is the recovery coefficient for that path.

You may assume that \(N\) and \(M\) are small (for example, \(N \le 8\) and \(M \le 10\)) so that an exhaustive search is feasible.

outputFormat

Output a single integer: the maximum number of mushrooms that can be collected starting from bush \(S\).

sample

3 3 1
1 2 4 0.7
2 3 3 0.5
1 3 2 0.9

7