This page is still under construction.

Parts of this page are still being built. What you see may change.

CN Tower 2

Time limit1sMemory limit128 MB

Summary
Choose a starting camera orientation so a rotating restaurant brings every landmark's bearing past the camera; minimize total time including flash recharge and the final recharge.
Level

Medium7 of 10

Topics
Sorting, Greedy, Math, Two pointers
Solved
No attempts yet

Problem

Christy is sightseeing in Toronto and wants to photograph the city's landmarks from the CN Tower. The tower's "360" restaurant sits 351 m above the ground and makes one full 360-degree rotation every 72 minutes. Christy chooses a single spot beside a window and always aims her camera exactly perpendicular to the glass, so as the restaurant turns, the compass direction her camera faces sweeps steadily around. She may pick her initial orientation instantly, but after that she can only wait for the restaurant to bring each landmark's bearing in front of her camera, and she never changes seats.

She reaches the top at 9:36 pm, when it is already dark, so every photo needs a powerful flash. After each photo the flash must recharge, and she cannot take another picture until it has finished charging. If several landmarks lie at exactly the same compass bearing, each still needs its own photo (only one landmark can be kept in focus per shot), so they cannot share a single exposure. After her final photo she must remain until the flash finishes recharging one last time.

Determine the minimum number of seconds Christy must stay in the restaurant to photograph every landmark. The restaurant closes at midnight; if she cannot photograph all of them before it closes, report that instead.

Input

The first line contains an integer nn (1≤n≤10001 \le n \le 1000), the number of landmarks Christy wants to photograph.

Each of the next nn lines describes one landmark: its name (a string of uppercase and lowercase letters), a single space, then its compass bearing from the CN Tower in degrees (00 = north, 9090 = east, 180180 = south, 270270 = west), given with at most two decimal places.

The last line contains the flash's recharge time, in seconds.

Output

Print a single integer: the minimum number of seconds Christy must stay in the restaurant. If that time is not a whole number of seconds, round it up to the next whole second. If she cannot photograph every landmark before the restaurant closes at midnight, print not possible instead.

Examples1

  1. Example 1

    Input
    5
CasaLoma 231
OntarioParliament 123
SkyDome 75
RoyalYorkHotel 340
PearsonAirport 165
10
    Expected output
    3022