You have been asked by the Payroll department to create a program that will calculate the weekly pay for the company's 25 employees. The program will prompt the user to provide each employee's full name, hourly pay rate, and hours worked. The program will then ask if the employee is single or married. If an employee is married, the tax rate is 25%; if they are single, the tax rate is 20%. Also, if the employee worked more than 40 hours in a week, the number of hours greater than 40 is paid at a rate of 1.5 times of the provided tax rate.

The program will display a list of all the employee names and weekly pay. In addition, the program will display the total payroll for the week and the average weekly pay.

Design a program using structured pseudocode as demonstrated in the lectures and, ensuring all variables are declared, prompt the user for the appropriate input and display a meaningful output message.

Ensure the following input is validated as follows:
If the hours worked per week is less than zero, set the hours worked to zero.
If the hours worked per week is greater than 80, set the hours worked to 80.
If the pay rate is less than $10 per hour, set the pay rate to 10.
If the pay rate is greater than $50, set the pay rate to 50.

Provide a program introduction message that tells the user how to use the program.