AIOC Banner

Problem: Dating Site IT

Want to try solving this problem? You can submit your code online if you log in or register.

Dating Site IT

Time Limit: 3 seconds
Memory Limit: 64 MB

You run an online dating site with many users. You keep detailed statistics for each user, including the number of times they visit your site this month. You would like to know how many visits your site gets in total this month. Unfortunately this is not as easy as it sounds – some of your users are spammers, who use your site to advertise their own products. You do not want to count the spammers' visits towards your total.

When a user registers with the site, they must supply many personal details including their age, height and weight. Spammers lie about these details, but they are very predictable and you can use their fake answers to spot them. For example, you might know that "any user whose age is between 18 and 30, whose height is between 80cm and 90cm, and whose weight is between 40kg and 50kg is a spammer".

Your task is to write a computer program that takes a number of statements like the above and a list of user statistics, and outputs the total number of visits your site has received this month.


Your program must read from standard input. In the description below, ai hi wi vi represent a user's age, height, weight and number of visits this month, respectively.

The first line will consist of two space-separated integers, S and U (1 ≤ S,U ≤ 1,000,000). Each of the following S lines will be of the form "aminamaxhminhmaxwminwmax", representing the statement "any user that satisfies amin ≤ aX ≤ amax and hmin ≤ hX ≤ hmax and wmin ≤ wX ≤ wmax is a spammer". (Of course, amin ≤ amax and so on). Following this will be U lines describes a single user, in the form "ai hi wi vi".

All ages, heights and weights are integers between 0 and 99 inclusive. Each user will make between 1 and 1000 visits, inclusive.

See the Scoring section for a breakdown of the marks awarded for different test cases.


Your program must write to standard output. The output should consist of a single integer: the number of visits made to your site this month by users who are not spammers.

Sample Input

2 3
18 24 30 60 80 85
21 30 40 50 0 99
18 30 80 3
25 35 86 5
23 45 82 7

Sample Output



The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

The following table lists the sizes of the inputs used in the test data. Here, N-1 is the maximum age, height and weight specified in the input.

N S U Percentage of marks
20 10 1000 10%
20 100 8000 10%
10 10000 100000 10%
30 10000 1000000 10%
50 100000 100000 20%
100 1000000 500000 20%
100 1000000 1000000 20%


Privacy statement
© Australian Mathematics Trust 2001-2019

Page generated: 24 May 2019,  3:55am AEST