思考题 for 300iq

Little Town Hero

If you prefer easier version, please move to Ep 28.5
XGN is playing the new game Little Town Hero(LTH) recently, but he is too stupid to beat the bosses. So he askes Orange Boy to help him.
In each turn, the player has N Dazzits(skills) and the enemy has M Dazzits.
Each Dazzit of yours has two parameters: a_i and c_i - the power of it and cost of it.
Each Dazzit of your enemy's has 1 parameter as well: b_i - the defense of it.
When two Dazzits meet, the enemy Dazzit will break if the power is greater or equal to the defense.
You can choose M different Dazzits to fight the enemy. You can only choose a sequence of Dazzits if the sum of their cost doesn't exceed a given integer pow. After you've done this, the enemy will arrange its Dazzits in totally random order. Then the Dazzits will meet one pair by one pair.
We call the enemy's Dazzits all break if all of its Dazzits are broken. What's the maximum possibility of all break if XGN chooses his Dazzits optimally?

Examples

Input
XGN={{3,1},{4,2},{2,0},{5,3},{6,6}} pow=3
Enemy={4,3}
Output
0.5
Explain
If XGN chooses {{3,1},{4,2}}:
Enemy - {3,4}(all break) {4,3}(break 0)
All break possibility 50%
If XGN chooses {{3,1},{2,0}}
Enemy - {3,4}(break 1) {4,3}(break 0)
All break possibility 0%
If XGN chooses {{4,2},{3,1}}
Enemy - {3,4}(break 1) {4,3}(all break)
All break possibility 50%
If XGN chooses {{4,2},{2,0}}
Enemy - {3,4}(break 1) {4,3}(break 1)
All break possibility 0%
If XGN chooses {{2,0},{5,3}}
Enemy - {3,4}(break 1) {4,3}(break 1)
All break possibility 0%
If XGN chooses {{5,3},{2,0}}
Enemy - {3,4}(break 1) {4,3}(break 0)
All break possibility 0%
So optimally, When XGN chooses {{4,2},{3,1}} or stuff like this, he can get 50% of all break.

Constriants

Subtask 1:n<=5,m<=5
Subtask 2:n<=8,m<=8
Subtask 3:n<=20,m<=20
Subtask 4:n<=100,m<=100, 0<=all integers inputted<=1000000