D. Infinite August
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Kira loves summer holidays: she can rest, go for walks, and not go to school. But August ends too quickly, and already on September 1 she has to go back to classes.

So Kira came up with her own calendar, in which August lasts forever. After August 31 comes August 32, then August 33, and so on. The holidays continue!

But an important problem arose: Kira's birthday is on December 6. She is not going to skip it, so she needs to find out what day number of August this date will become. For example, if we extend August 2026, Kira's birthday will fall on August 128.

Kira decided that in this way any month can be extended, and any later date can be converted into her calendar: choose a month $$$m$$$ and a year $$$y$$$, after which month $$$m$$$ of year $$$y$$$ becomes infinite — it is followed by "$$$($$$ day of month $$$+1)$$$-th $$$m$$$", then "$$$($$$ day of month $$$+2)$$$-th $$$m$$$", and so on, without moving on to the following months and years.

The first day of month $$$m$$$ of year $$$y$$$ is day number $$$1$$$ in Kira's calendar, the next day is number $$$2$$$, and so on: each next calendar day gets a number one greater than the previous one.

You are given the chosen month $$$m$$$ and year $$$y$$$, as well as a date in the usual (Gregorian) calendar: day $$$d$$$, month $$$m_2$$$, year $$$y_2$$$. Determine the day number of this date in Kira's calendar, that is, the number this date gets if month $$$m$$$ of year $$$y$$$ is extended infinitely.

The Gregorian calendar is used: read the note for details about the number of days in months and leap years.

Input

The first line contains two integers $$$m$$$ and $$$y$$$ $$$(1 \le m \le 12,\ 1 \le y \le 9999)$$$ — the number of the month and the number of the year Kira chose to extend.

The second line contains three integers $$$d$$$, $$$m_2$$$, and $$$y_2$$$ $$$(1 \le m_2 \le 12,\ 1 \le y_2 \le 9999)$$$ — the day, month, and year of the date for which the day number in Kira's calendar must be determined.

It is guaranteed that the date $$$d$$$, $$$m_2$$$, $$$y_2$$$ exists in the Gregorian calendar (the rules for determining the number of days in a month and leap years are given in the note) and is not earlier than the first day of month $$$m$$$ of year $$$y$$$.

Output

Print one integer — the day number of the date $$$d$$$, $$$m_2$$$, $$$y_2$$$ in Kira's calendar, where the first day of month $$$m$$$ of year $$$y$$$ has number $$$1$$$, the next calendar day has number $$$2$$$, and so on.

It is guaranteed that under the given constraints the answer always exists and is uniquely determined.

Examples
Input
8 2026
6 12 2026
Output
128
Input
8 2026
1 8 2026
Output
1
Input
2 2024
1 3 2024
Output
30
Input
12 3456
11 1 3457
Output
42
Input
6 7
8 9 1023
Output
371186
Note

The Gregorian calendar is used.

A year is a leap year if its number is divisible by $$$400$$$ or divisible by $$$4$$$ but not divisible by $$$100$$$.

In a leap year, February has $$$29$$$ days; in other years — $$$28$$$ days. April, June, September, and November have $$$30$$$ days, and the remaining months have $$$31$$$ days.

Note — although historically the Gregorian calendar appeared only in the 16th century, in this problem its leap-year rules apply to all valid year values.

In the first example, August 2026 is chosen, and the given date is December 6, 2026. From August 1 to December 1, 2026, August ($$$31$$$ days), September ($$$30$$$ days), October ($$$31$$$ days), and November ($$$30$$$ days) pass, for a total of $$$31 + 30 + 31 + 30 = 122$$$ days, so December 1 is August $$$123$$$. Then December 6 becomes August $$$123 + 5 = 128$$$, which matches the answer $$$128$$$.

In the second example, the given date is August 1, 2026, that is, exactly the first day of the chosen month. By definition, it gets number $$$1$$$ in Kira's calendar, which matches the answer $$$1$$$.

In the third example, February 2024 is chosen, and the given date is March 1, 2024. The year $$$2024$$$ is divisible by $$$4$$$ and not divisible by $$$100$$$, so it is a leap year, and February 2024 has $$$29$$$ days. Therefore, March 1 comes the day after February 29, that is, it becomes February $$$30$$$ in Kira's calendar, which matches the answer $$$30$$$.

In the fourth example, December 3456 is chosen, and the given date is January 11, 3457. The answer is $$$42 = 31 + 11$$$, which is also the answer to the "Ultimate Question of Life, the Universe, and Everything".

You can use the fifth test case to check your solution on large time intervals.