Reviewers of Electronic Designs ∼ International Service (REDIS) is an organization that invests in electronic designs. Some time ago, REDIS invented an electronic device, called Asynchronous Commu- nication Internal Switch (ACIS), that is built connecting some components in series. In order to ensure the proper function of ACIS, it is required that all components work correctly. For that purpose, inside each component can be installed a fixed number of regulators, decreasing the probability of failure of ACIS. in 1 2 3 ··· N out Components connected in series on ACIS. For each component in ACIS, REDIS defines the maximum number of regulators that can be installed inside it. Also, for each component and for each possible number of regulators that can be installed inside that component, REDIS specifies the cost of installing that number of regulators inside the component, and the probability of failure of the component if it were installed that number of regulators inside it. For each component, it is guaranteed that the cost is strictly increasing on the number of regulators, and that the probability of failure is strictly decreasing on the number of regulators. The Financial Manager of REDIS has hired you to design ACIS, minimizing its probability of failure. Given a specific budget, you must decide how many regulators you should install inside each component, in order to minimize the probability of failure of ACIS, ensuring that the total cost of your investment does not exceed the given budget. Input The input consists of several test cases, each one describing a distinct electronic device. The first line of a test case contains two blank-separated integers N and K indicating, respectively, the number of components connected on ACIS (1 ≤ N ≤ 8), and the budget you have to invest (0 ≤ K ≤ 1000). The second line of a test case contains exactly N blank-separated integers M1, M2, . . . , MN , where Mi denotes the maximum number of regulators that can be installed inside the i-th component (1 ≤ Mi ≤ 16), for each 1 ≤ i ≤ N. Then N lines follow, each one describing a component: line i contains exactly 3 · Mi blank-separated integers αi1, βi1, γi1, αi2, βi2, γi2, . . . , αiMi , βiMi , γiMi , where γim is the cost of installing m regulators inside the i-th component (1 ≤ γim ≤ 1000, for each 1 ≤ m ≤ Mi), and αim/βim is the probability of failure of the i-th component if it were installed m regulators inside it (0≤αim <βim ≤100,foreach1≤m≤Mi). You can assume, for each component i, that: • The cost of installing regulators inside that component, is strictly increasing on the number of regulators (i.e., 0 < γi1 < γi2 < ··· < γiMi). • The probability of failure of that component if it were installed regulators inside it, is strictly decreasing on the number of regulators (i.e., 1 > αi1/βi1 > αi2/βi2 > · · · > αiMi /βiMi ). • The cost of installing 0 regulators inside that component is 0. • The probability of failure of that component is 1 if it were installed 0 regulators inside it.
2/2 Output For each test case, print a line of the form ‘a/b’, where a, b are integers such that 0 ≤ a ≤ b, b > 0, gcd(a, b) = 1, and the fraction a/b is the minimum probability of failure of ACIS with the constraints given. Note that, if such probability is 0, you must print ‘0/1’. Sample Input 1 50 1 0 1 100 1 100 1 0 1 100 2 300 23 2 3 10 1 10 100 9 10 100 1 2 200 1 5 250 2 100 23 2 3 10 1 10 100 9 10 100 1 2 200 1 5 250 Sample Output 1/1 0/1 11/20 1/1