Weekly Calendar

A weekly calendar is a calendar that holds the schedule for 7 days, from Sunday to Saturday.

Last year, Suhyeon used a one-year calendar with coated paper attached to it. This year she is a bit smarter and wants to mark her schedule on a weekly calendar using tape. Alas, she has only N weekly calendars but M schedule entries. Holding back her tears, she wants to use the weekly calendars as fully as possible.

There is no limit on the number of schedule entries that can go on one weekly calendar, and the N weekly calendars must be consecutive. The first date of the weekly calendars must be at least 1, and the day of the week does not matter. A schedule entry is marked with tape, and we assume that no tape is cut unnecessarily to mark a single schedule entry. For example, when marking one schedule entry on one weekly calendar, it is not split into several pieces and taped on.

Find the number of tape cuts when the tape takes up the largest area of the weekly calendars. If there are two or more cases where the tape takes up the largest area, find the number of tape cuts among those cases where the starting date of the weekly calendars is the smallest.

Look at the figure below.

As with the light blue and gray schedule entries, if any part of a schedule entry is included in the weekly calendars, it counts toward the number of schedule entries. However, the area is calculated only for the region inside the weekly calendars.

The green schedule entry is included in two weekly calendars. Therefore, for the green schedule entry, the tape must be cut twice.

In the example above, the total number of tape cuts is 10. The reason is shown in the figure below.

The first line gives the number of weekly calendars N. (1 ≤ N ≤ 100)

The second line gives the number of schedule entries M. (1 ≤ M ≤ 1,000)

The following M lines give the start date S and the end date E. (1 ≤ S ≤ E ≤ 50,000)

Print the total number of tape cuts.

The day of the week does not matter.