An hourglass is given as a tuple (upper, lower) for the number of minutes of sand that are currently stored in its upper and lower chambers, both chambers large enough to hold all of the sand in that hourglass. So after m minutes of time has elapsed, the state of that particular hourglass will be upper - min(upper, m), lower + min(upper, m). The total amount of sand inside the hourglass never changes, nor will either chamber ever contain negative anti-sand.

Given a list of glasses, your task is to find an optimal sequence of moves to measure exactly t minutes, scored as the number of individual hourglass flips performed along the way. Each move consists of two stages:

• you must first wait for the hourglass that currently holds the lowest non zero amount m of sand in its upper chamber to run out.
• when that happens, choose any subset of glasses and instantaneously flip this chosen subset.

Look at the example for [(7, 0), (11, 0)], 15 case. You can find an explanation for slightly changed case in a Popular Mechanics article.

You don’t have any choice in waiting in the first stage, but in the second stage you enjoy an embarrassment of riches of 2ⁿ – 1 possible moves for n glasses!

This function should return the smallest possible number of individual hourglass flips needed to measure exactly t minutes, or None if this exact measurement is impossible.

Input: Two arguments: list of tuples of two integers (int), integer.

Output: Integer or None.

Examples:

assert hourglass_flips([(1, 0), (2, 0)], 2) == 0
assert hourglass_flips([(7, 0), (11, 0)], 15) == 2
assert hourglass_flips([(4, 0), (6, 0)], 11) == None
assert hourglass_flips([(7, 1), (10, 4), (13, 1), (18, 4)], 28) == 3

The mission was taken from Python CCPS 109. It is taught for Ryerson Chang School of Continuing Education by Ilkka Kokkarinen