토트

오스탑은 리우에 도착하자마자 흰색 바지를 샀다. 그다음으로 한 일은 밀반입한 돈 전부를 현지 축구 토트에 탕진하는 것이었다.

주 챔피언십에서는 $n$개의 경기가 열리며, 각 경기는 승리, 무승부, 패배의 세 가지 결과 중 하나를 가질 수 있다.

토트 티켓에는 모든 경기의 목록이 적혀 있다. 티켓을 산 직후 구매자는 각 경기에 어떤 결과에 베팅할지 표시해야 한다. 경기마다 결과 하나를 표시할 수도 있고(소위 "단식"), 두 결과를 표시할 수도 있으며("복식"), 세 결과를 모두 표시할 수도 있다("삼식").

여러 종류의 티켓이 판매된다. 티켓의 종류는 가격과 두 정수 $i$, $j$로 정의된다. 구매자는 티켓에 정확히 $i$개의 복식, 정확히 $j$개의 삼식, 정확히 $n-i-j$개의 단식을 넣어야 한다. 단식, 복식, 삼식을 경기별로 어떻게 배분하고 어떤 결과에 베팅할지는 구매자가 선택할 수 있다.

구매자가 $n$개 경기의 결과를 모두 맞히면, 그 승리 티켓에 대해 $P$코인을 받는다. 운이 없었다면 아무것도 받지 못한다. 구매자는 티켓에 그 경기에서 실제로 일어난 결과가 표시되어 있을 때에만 그 경기의 결과를 맞힌 것이다.

도박의 악마 벨리알과 아는 사이인 덕분에 오스탑은 모든 경기의 결과가 무작위로 결정된다는 것을 안다. 오스탑은 모든 결과의 확률까지 알아냈다. 게다가 $n$개 경기의 결과는 서로 독립적으로 결정된다는 것도 안다.

오스탑에게는 티켓에 쓸 수 있는 $S$코인만 남아 있다. 단골이므로 오스탑은 가진 코인이 가격을 감당할 수 있는 한, 판매되는 각 종류의 티켓을 원하는 만큼 살 수 있다. 이제 남은 일은 상금의 기댓값이 최대가 되도록 돈을 현명하게 배분하는 것이다. 오스탑은 돌려받을 상금을 최대화하며, 티켓에 드는 비용이 얼마인지는 상관하지 않는다.

입력 파일의 첫 줄에는 네 정수 $n$, $k$, $S$, $P$가 주어진다. $n$은 경기의 수, $k$는 티켓 종류의 수, $S$는 오스탑이 가진 코인의 수, $P$는 승리 티켓에 주어지는 코인의 수다($1 \le n,k \le 100$, $1 \le S \le 10^6$, $1 \le P \le 10^{18}$).

다음 $n$개 줄에는 각 경기 결과의 확률이 주어진다. 이 중 $i$번째 줄에는 소수점 이하 최대 8자리의 실수 $x\_i$, $y\_i$, $z\_i$가 주어지며, 각각 $i$번째 경기에서 승리, 무승부, 패배의 확률이다($0 \le x\_i, y\_i, z\_i \le 1$, $x\_i + y\_i + z\_i = 1$).

다음 $k$개 줄에는 판매되는 티켓의 종류가 주어진다. 각 줄에는 세 정수 $i$, $j$, $c\_{ij}$가 주어진다. $i$와 $j$는 각각 그 종류의 티켓에 표시해야 하는 복식과 삼식의 수이고, $c\_{ij}$는 그 종류의 티켓 한 장의 가격이다($0 \le i, j \le n$, $i+j \le n$, $1 \le c\_{ij} \le 10^6$).

상금의 기댓값의 최댓값을 나타내는 실수 하나를 출력한다.

답의 절대 오차 또는 상대 오차는 $10^{-9}$를 넘지 않아야 한다.

첫 번째 예시에서 첫 번째 종류의 티켓은 단식만 허용한다. 두 경기 모두 승리를 표시하면 그 티켓은 40%의 확률로 당첨된다. 따라서 이 종류의 티켓 한 장에서 얻는 상금의 기댓값은 4이다.

두 번째 종류의 티켓에는 복식이 하나 있어야 한다. 이런 티켓을 가장 잘 쓰는 방법은 첫 번째 경기에 복식을 표시해 승리와 무승부에 베팅하고, 두 번째 경기에 단식을 표시해 승리에만 베팅하는 것이다. 그러면 티켓은 64%의 확률로 당첨되며, 평균 6.4코인의 상금을 준다.

오스탑에게는 10코인만 남아 있다. 각 종류의 티켓을 한 장씩 당첨시키는 것이 그가 할 수 있는 최선이다.