JAPLJの住む町にある植物園では長方形状の土地に花を規則的に植えることで美しい模様を作り出している。その中でも特にナデシコが織り成す模様は非常に美しく人気がある。植物園ではこの模様を定期的に植え替えることでより多くの人が植物園に来るようにしたいと思っている。
模様を植える土地は長方形状であり、横には W 本、縦には H 本のナデシコを植えられる余裕がある。この土地を W*H 個の合同な小正方形に区切り、その小正方形ひとつ(これを区画と言おう)にナデシコを1本植えるものとして考える。全体の土地のうち、左から数えて a 個目、上から数えて b 個目の区画を (a, b) と表すことにする。また、この植物園が所有しているナデシコは花の大きさごとに分類されており、花の大きさをうまく使い分けることで抑揚のある模様を作ることができる。
模様を作るために何種類かのパターンが用意されている。パターンとは一辺の長さが d の正方形であり、d*d 個のマス目に分かれているものである。それぞれのマス目には花を植えるか植えないかのどちらかであり、植える場合にはどの大きさの花を植えるかも決まっている。模様を作る際にはパターンを一種類選び、そのパターンを横に何回か、縦に何回か繰り返してより大きな長方形を作る。
さて、この植物園では今後の植え替えのスケジュールを立てており、どのような模様を植えるのかは今後 N 回分について決まっている。しかしここでひとつ問題が発生した。あまりに長い間花を植えておくとその部分の土壌が痩せてしまうため、ひょっとすると N 回分のスケジュールを敢行することは不可能かもしれないというのである。
土壌の肥沃度は次のようにして計算される。はじめ、どの区画もその部分の肥沃度は一律 F である。ある区画に大きさ P のナデシコが植えられるたびに、その部分の肥沃度は P だけ下がる。そして、ある模様を植える際にどの1つの区画でも肥沃度が0を下回るならば(負の値になるならば)その模様を実際に植えることはできないとする。
土地についての情報、N回分のスケジュールが与えられると、そのスケジュールが敢行できるかどうかを判定するプログラムを書け。ただしスケジュールは与えられる順番で実行しなければならないものとする。
入力の最初の1行には5つの整数 N (1 <= N <= 100000 = 105), W, H (1 <= W, H <= 1000), d (1 <= d <= 10), F (1 <= F <= 1000000 = 106) がこの順に、空白区切りで書かれている。 N はスケジュールの数、 W および H は土地の大きさ、 d はパターンの大きさ、 F は区画の最初の肥沃度を表す。その後に N 個分のスケジュールの情報が続く。
1つのスケジュールの情報の最初の1行には4つの整数 a (1 <= a <= W), b (1 <= b <= H), x, y が書かれている。これは模様の左上端の区画が全体の土地において (a, b) の区画に植えられ、その模様は与えられるパターンを横に x 回、縦に y 回繰り返したものであることを表す。全ての a, b, x, y の組は模様が土地からはみ出ないようになっていることが保障されている。
続く d 行にはパターンの情報が書かれている。各行には d 文字の文字列が書かれており、 i 行目の j 番目の文字はパターンにおける (j, i) の区画を表す。文字列は ".123456789" の10種の文字のみで構成されている。文字 '.' はその区画にナデシコを植えないことを表し、それ以外の数字はその区画に植えるナデシコの大きさを表す。
1行出力せよ。その1行には土地の肥沃度が 0 を下回らない範囲でこなすことのできるスケジュールの数が書かれていなければならない。
採点用データのうち、配点の 15% 分は N <= 100, W <= 100, H <= 100 を満たす。
採点用データのうち、配点の 30% 分は N <= 500 を満たす。
採点用データのうち、配点の 45% 分は N <= 2500 を満たす。
採点用データのうち、配点の 60% 分は N <= 20000 を満たす。
3 20 20 4 7 9 1 3 2 6173 5661 .251 5156 16 12 1 1 5868 7546 9783 2169 5 1 1 2 8394 9.18 2573 5145
2
5 10 10 3 10 8 1 1 2 617 356 61. 1 8 1 1 156 854 458 3 7 2 1 469 783 216 2 3 1 1 183 949 .18 7 4 1 2 514 552 872
3