Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thô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