There are n commodities numbered from 1 to n . The commodities are traded at multiple exchanges where each exchange only allows a particular pair of commodities to be exchanged. There are total n-1 exchanges. The commodities and the exchanges form a tree structure.

ith exchange charges ti units as a transaction charge for its services, e.g. say a particular exchange allows trade between commodity a and b, and you are exchanging 10 units from a to b or vice versa and if it charges 2 units, then you can get 8 units of b corresponding to 10 units of a and vice versa. The trader performing the transaction earns pi profit as a result of transaction.

A trader wants to maximize the profit and is allowed to start with m units of any commodity of his/her choice.

Can you find the maximum profit the trader can earn if he/she can trade with any exchange at most once?

Input Format : The first line contains two integers n and m. Then n-1 lines follow. Each line describes an exchange allowing trade between two commodities It contains four integers, ui, vi, ti and pi. ui and vi are the numbers of two commodities traded at this exchange, ti is the transaction charge, and pi is the profit trader makes by trading at this exchange.

Output Format

An integer which is the maximum profit.

Sample Input :

5 4 1 2 1 2 1 3 2 3 1 4 2 4 4 5 2 2

Sample Output : 7

Explanation : You start with 4 units of commodity numbered 3 and exchange it with 1 at the expense of 2 units and earning 3 profit. Then, you exchange 1 with 4 at the expense of remaining 2 units and earning 3 profit. So, total profit earned is 7.