CF566G.Max and Min
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Two kittens, Max and Min, play with a pair of non-negative integers x and y . As you can guess from their names, kitten Max loves to maximize and kitten Min loves to minimize. As part of this game Min wants to make sure that both numbers, x and y became negative at the same time, and kitten Max tries to prevent him from doing so.
Each kitten has a set of pairs of integers available to it. Kitten Max has n pairs of non-negative integers (ai,bi) ( 1<=i<=n ), and kitten Min has m pairs of non-negative integers (cj,dj) ( 1<=j<=m ). As kitten Max makes a move, it can take any available pair (ai,bi) and add ai to x and bi to y , and kitten Min can take any available pair (cj,dj) and subtract cj from x and dj from y . Each kitten can use each pair multiple times during distinct moves.
Max moves first. Kitten Min is winning if at some moment both numbers a , b are negative simultaneously. Otherwise, the winner of the game is kitten Max. Determine which kitten wins if both of them play optimally.
输入格式
The first line contains two integers, n and m ( 1<=n,m<=100000 ) — the number of pairs of numbers available to Max and Min, correspondingly.
The second line contains two integers x , y ( 1<=x,y<=109 ) — the initial values of numbers with which the kittens are playing.
Next n lines contain the pairs of numbers ai,bi ( 1<=ai,bi<=109 ) — the pairs available to Max.
The last m lines contain pairs of numbers cj,dj ( 1<=cj,dj<=109 ) — the pairs available to Min.
输出格式
Print «Max» (without the quotes), if kitten Max wins, or "Min" (without the quotes), if kitten Min wins.
输入输出样例
输入#1
2 2 42 43 2 3 3 2 3 10 10 3
输出#1
Min
输入#2
1 1 1 1 3 4 1 1
输出#2
Max
说明/提示
In the first test from the statement Min can respond to move (2,3) by move (3,10) , and to move (3,2) by move (10,3) . Thus, for each pair of Max and Min's moves the values of both numbers x and y will strictly decrease, ergo, Min will win sooner or later.
In the second sample test after each pair of Max and Min's moves both numbers x and y only increase, thus none of them will become negative.