Can my favourite team still become Football Champion? As a fan of an at most moderately successful footballBE team, towards the end of the season I often wonder whether my favourite team still has any theoretical chance left of becoming champion. Your task in this challenge is to answer that question for me. 

Input

You will recieve three inputs: the current table, the list of remaining matches, and the current position of the team we are interested in.

Input 1: The current table, a sequence of numbers were the i-th number are the points gained by team i so far. For example, the input
[93, 86, 78, 76, 75] encodes the following table (only the last column is of importance):





Input 2: The remaining matches, a sequence of tuples where each tuple (i,j) stands for a remaining match between team i and j. In the above example, a second input of [(1,2), (4,3), (2,3), (3,2), (1,2)] would mean that the remaining matches are:

Chelsea vs Tottenham, Liverpool vs Man. City, Tottenham vs Man. City, Man. City vs Tottenham, Chelsea vs Tottenham




Input 3: The current position of the team we are interested in. For example, an input of 2 for the above example would mean that we'd like to know whether Tottenham can still become champion.

Output

For each remaining match of the form (i,j), there are three possible outcomes:


Team i wins: Team i gets 3 points, team j gets 0 points
Team j wins: Team i gets 0 points, team j gets 3 points
Draw: Team i and j both get 1 point


You must output a truthy value if there is some outcome for all remaining games such that at the end, no other team has more points than the team specified in the 3rd input. Otherwise, output a falsy value.

Example: Consider the exemplary input from the above section:

Input 1 = [93, 86, 78, 76, 75],
Input 2 = [(1,2), (4,3), (2,3), (3,2), (1,2)],
Input 3 = 2

If team 2 wins all its remaining matches (i.e. (1,2), (2,3), (3,2), (1,2)), it gets 4*3 = 12 additional points; none of the other teams gets any points from these matches. Let's say the other remaining match (i.e. (4,3)) is a draw. Then the final scores would be:

 Team 1: 93, Team 2: 86 + 12 = 98, Team 3: 78 + 1 = 79, Team 4: 76 + 1 = 77, Team 5: 75


This means that we have already found some outcome for the remaining matches such that no other team has more points than team 2, so the output for this input must be truthy.

Details


You may assume the first input to be an ordered sequence, i.e. for i &lt; j, the i-th entry is equal to or greater than the j-th entry. The first input may be taken as a list, a string or the like.
You may take the second input as a string, a list of tuples or the like. Alternatively, you may take it as a two-dimensional array a where a[i][j] is the number of entries of the form (i,j) in the list of remaining matches. For example, a[1][2] = 2, a[2][3] = 1, a[3][2] = 1, a[4][3] = 1
corresponds to [(1,2), (4,3), (2,3), (3,2), (1,2)]. 
For the second and third input, you may assume 0-indexing instead of 1-indexing.
You may take the three inputs in any order.


Please specify the exact input format you chose in your answer.

Side node: The problem underlying this challenge was shown to be NP-complete in "Football Elimination is Hard to Decide Under the 3-Point-Rule". Interestingly, if only two points are awarded for a win, the problem becomes solvable in polynomial time.

Test Cases

All test cases are in the format Input1, Input2, Input3.

Truthy:


[93, 86, 78, 76, 75], [(1,2), (4,3), (2,3), (3,2), (1,2)], 2
[50], [], 1
[10, 10, 10], [], 3
[15, 10, 8], [(2,3), (1,3), (1,3), (3,1), (2,1)], 2


Falsy:


[10, 9, 8], [], 2
[10, 9, 9], [(2,3), (3,2)], 1
[21, 12, 11], [(2,1), (1,2), (2,3), (1,3), (1,3), (3,1), (3,1)], 2


Winner

This is code-golf, so the shortest correct answer (in bytes) wins. The winner will be chosen one week after the first correct answer is posted.
Haskell (Lambdabot), 84 bytes

Thanks to @bartavelle for saving me a byte.

Without Lambdabot, add 20 bytes for import Control.Lens plus a newline. 

The function takes its arguments in the same order as described in the OP, 0-indexed. Its second argument (the list of remaining matchups) is a flat list of indexes (e.g. [1,2,4,1] corresponds to [(Team 1 vs Team 2), (Team 4 vs Team 1)]). 

The rules are a little vague as to whether or not this is allowed. If it isn't allowed, the function can take input in the format provided by the examples – a list of tuples. In that case, add 2 bytes to this solution's score, due to replacing a:b:r with (a,b):r.



(!)=(+~).element
(t?(a:b:r))s=any(t?r)[a!3$s,b!3$s,b!1$a!1$s]
(t?_)s=s!!t==maximum s


Explanation:

The first line defines an infix function ! of three variables, of type (!) :: Int -&gt; Int -&gt; [Int] -&gt; [Int], which increments the value at a given index in a list. Since, oftentimes, code is easier to understand than words (and since Haskell syntax can be weird), here's a Python translation:



def add(index, amount, items):
    items[index] += amount
    return items


The second line defines another infix function ?, also of three variables (the challenge input). I'll rewrite it more readably here:


(t ? a:b:r) s = any (t ? r) [a ! 3 $ s, b ! 3 $ s, (b ! 1 $ a) ! 1 $ s]
(t ? _) s = (s !! t) == maximum s


This is a recursive implementation of exhaustive search. It recurs over the list of remaining games, branching on the three possible outcomes, and then, once the list is empty, checking whether or not our team has the maximum number of points. Again in (non-idiomatic) Python, this is:



def can_still_win(standings, games_left, our_team):
    if games_left == []:
        return standings[our_team] == max(standings)
    team1, team2, other_games = games_left[0], games_left[1], games_left[2:]
    team1Wins, team2Wins, tie = standings.copy(), standings.copy(), standings.copy()
    team1Wins[team1] += 3
    team2Wins[team2] += 3
    tie[team1] += 1
    tie[team2] += 1
    return (can_still_win(team1Wins, other_games, our_team)
            or can_still_win(team2Wins, other_games, our_team)
            or can_still_win(tie, other_games, our_team))


Try it online!

*Sadly, TiO doesn't support Lens, so this link won't actually run.