Y2K Accounting Bug

Time limit1sMemory limit128 MB

Summary
Given monthly surplus s and deficit d, find the maximum yearly total over all 12 months given that every 5-month block is negative, or report Deficit.
Level

Medium4 of 10

Topics
Brute force, Greedy, Math
Solved
No attempts yet

Problem

Accounting for Computer Machinists (ACM) was hit by the Y2K bug and lost some vital data needed to prepare the annual report for MS Inc.

Here is all ACM remembers. In each of the 12 months of 1999, MS Inc. posted either a surplus or a deficit. Every month that posted a surplus reported exactly ss, and every month that posted a deficit reported exactly dd, where ss and dd are positive integers. ACM does not remember which months were surplus months, nor how many surpluses or deficits there were.

Unlike other companies, MS Inc. reports its earnings over every block of 5 consecutive months. There are therefore 8 such blocks (months 1–5, 2–6, …, 8–12), and ACM knows only that all 8 of these blocks reported a deficit — that is, the total of every 5 consecutive months is negative. The size of each block's deficit is unknown.

Given ss and dd, decide whether MS Inc. could have finished the whole year of 1999 with a surplus (a positive total over all 12 months), and if so, report the maximum possible annual surplus. If no assignment of surplus and deficit months that satisfies the conditions above can make the annual total positive, the year is a deficit.

Input

The input consists of several lines. Each line contains two positive integers ss and dd separated by a space. Input continues until end of file.

Output

For each line of input, print one line. Print the maximum annual surplus as a positive integer, or print Deficit if no valid assignment can make the annual total positive.

Examples1

  1. Example 1

    Input
    59 237
    375 743
    200000 849694
    2500000 8000000
    
    Expected output
    116
    28
    300612
    Deficit