Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT128C - Bảo vệ bảo tàng

Một bảo tàng thuê một số bảo vệ và muốn xây dựng lịch biểu cho họ. Người ta muốn lịch biểu này phải thỏa mãn trông coi được cả 24h và:

  • Mỗi bảo vệ làm việc cùng một khoảng thời gian mỗi ngày.
  • Mỗi bảo vệ muốn làm việc trong một khoảng thời gian mà người đó đưa ra.
  • Mỗi bảo vệ cũng chỉ làm việc trong tổng thời gian tối đa mà người đó thông báo trước.
  • Các bảo vệ chỉ đổi ca tại các điểm chẵn nửa giờ (ví dụ 4h00 hoặc 4h30 nhưng không được là 4h15).
  • Các bảo vệ chỉ đổi ca nếu thời gian đổi ca đó nằm trong thời gian sẵn sàng của họ.
  • Số lượng bảo vệ tối thiểu tại một thời điểm bất kỳ trong ngày phải càng lớn càng tốt để tăng cường khả năng an ninh cho bảo tàng. 

Hãy viết chương trình giúp bảo tàng tìm ra giá trị lớn nhất của số bảo vệ tối thiểu có mặt tại tất cả các thời điểm trong ngày.

Input

Gồm nhiều bộ test, mỗi bộ test gồm:

  • Dòng 1 ghi số N là số bảo vệ (1<=N<=50)
  • Tiếp theo sẽ là mô tả của N bảo vệ. Mỗi mô tả gồm
    • Một dòng ghi hai số K và M. Trong đó K là số khoảng thời gian trong ngày mà bảo vệ đó sẵn sàng (1<=K<=50). Còn M là số phút tối đa mà anh ta có thể làm việc trong ngày (1<=M<=1440).
    • K dòng tiếp theo chứa thời gian bắt đầu và kết thúc của mỗi khoảng mà bảo vệ đó sẵn sàng theo định dạng HH:MM (theo chuẩn 24h).

Dữ liệu vào kết thúc với dòng chứa số 0

Output

Với mỗi bộ test ghi trên một số nguyên là số bảo vệ tối thiểu có mặt tại mỗi thời điểm bất kỳ trong ngày (chú ý cần tìm ra giá trị lớn nhất có thể của số này).

Example

Input:

3

1 540

00:00 00:00

3 480

08:00 10:00

09:00 12:00

13:00 19:00

1 420

17:00 00:00

5

1 720

18:00 12:00

1 1080

00:00 23:00

1 1080

00:00 20:00

1 1050

06:00 00:00

1 360

18:00 00:00

3

1 1440

00:00 00:00

1 720

00:00 12:15

1 720

12:05 00:15

0 Output:

1

2

1

Được gửi lên bởi:adm
Ngày:2012-04-04
Thời gian chạy:2.068s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2013-12-13 10:55:48 an IM3 Ex-Member of Bit
đề bài gốc tiếng anh: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2603
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.