Problem1491--VIJOS-P1246

1491: VIJOS-P1246

Time Limit: 0 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

        这学期的政治、历史和地理课本各有n章。每一科的教学必须按章节从前往后依次进行。若干章政治、若干章历史和若干章的地理内容可以合成一个教学阶段。年级计划将整个学期的内容分成若干个阶段进行教学。为了保证各科教学进度相同,年级规定每一个阶段包含的各科的章节数必须相同。一个阶段包含的章节越多,这个阶段所需要的课时也就越多。经过研究,假如某个阶段包含政史地各k章,则政治学习需要花费3^k天的课时,历史学习需要花费5^k天的课时,地理学习需要花费2^k天的课时,最后还需要4天的综合训练。一个阶段所花费的总时间是以上四项时间的和。         为了便于安排时间,学校希望每个阶段恰好需要若干周来完成。因此,划分出的每一个阶段所需要的天数都必须是7的整数倍(高三是没有星期六和星期天的)。         那么,这学期的课程最多可以划分成多少个阶段呢?你会想到,要想划分的阶段数最多,一个阶段完成一章的任务就行了(因为3^1+5^1+2^1+4=14是7的整数倍)。但问题没有这么简单。每个课本都可能有一些独立性较强的连续章节,它们具有很强的连续性,必须在一个阶段中完成。如果你已知所有不能划分在两个或两个以上的阶段中的连续章节,你还能计算出最多能安排多少个阶段吗?

Input

        第一行有两个用空格隔开的正整数n和m,分别表示各科课本的章节数和不可分割的连续章节的个数。         第二行到第m+1行,每行告诉了一个信息,该信息说明了哪一个课本的第几章到第几章必须一次性完成。同一科目给定的章节有可能重复或有重叠。         每一行信息分为两个部分。第一部分是“Politics:”、“History:”、“Geography:”三个字符串中的一个;第二部分是用“-”连接的两个数字x,y(1< =x< y< =n),表示该行第一部分所示的课本从第x章到第y章具有连续性。第二部分紧接在第一部分后面,没有任何符号分隔。         对于30%的数据,n,m< =10;         对于50%的数据,n,m< =1000;         对于100%的数据,n,m< =100  000。

Output

        一个正整数,表示按照学校和年级的种种要求(见下)最多可以安排的阶段个数。         如果没有符合条件的安排方案,请输出-1。         注意:以下三个要求需要同时考虑。                 1.每一个阶段包含的各科章数相同;                 2.按时间函数计算出的各阶段所需天数必须是7的倍数;                 3.给出的任一个连续章节都不能被分割开来。

Sample Input Copy

8 3
Politics:1-2
History:5-6
Politics:1-4

Sample Output Copy

3

HINT

样例说明:         最多可以安排三个阶段,具体方案如下:         第一阶段完成各科第1-6章的课程         第二阶段完成各科第7章的课程         第三阶段完成各科第8章的课程 Sample  Input  #2: 4  2 Geography:1-3 History:2-4 Sample  Output  #2: -1

Source/Category